Volker Strassen
Volker Strassen | |
|---|---|
 Volker Strassen giving the Knuth Prize lecture at SODA 2009 | |
| Born | April 29, 1936 |
| Nationality | German |
| Alma mater | University of Göttingen |
| Scientific career | |
| Fields | Mathematics, Statistics, Computer Science |
| Doctoral advisor | Konrad Jacobs |
| Doctoral students | Walter Baur Peter Bürgisser Joachim von zur Gathen Joos Ulrich Heintz |
Volker Strassen (born April 29, 1936) is a German mathematician, a professor emeritus in the department of mathematics and statistics at the University of Konstanz.[1]
For important contributions to the analysis of algorithms he has received many awards, including the Cantor medal,[2] the Konrad Zuse Medal,[3] the Paris Kanellakis Award for work on randomized primality testing,[4] the Knuth Prize for "seminal and influential contributions to the design and analysis of efficient algorithms."[5]
Biography
[edit]
Strassen was born on April 29, 1936, in Düsseldorf-Gerresheim. [2]After studying music, philosophy, physics, and mathematics at several German universities,[2] he received his Ph.D. in mathematics in 1962 from the University of Göttingen under the supervision of Konrad Jacobs.[6] He then took a position at the department of mathematics and later at the department of statistics at the University of California, Berkeley, where he eventually became an associate professor.
In 1968, Strassen moved to Zurich as the director of the Seminar (later Institute) for Applied Mathematics. He remained at the University of Zurich for twenty years before moving to the University of Konstanz in 1988.[2] He retired in 1998.[4]
Research (selected papers)
[edit]Strassen began his research as a probability theorist with his 1964 paper An Invariance Principle for the Law of the Iterated Logarithm. Strassen's law of the iterated logarithm has been widely cited and led to a 1966 presentation at the International Congress of Mathematicians in Moscow.
In 1965, Strassen published The Existence of Probability Measures with Given Marginals. In this paper, he derived necessary and sufficient conditions for a sequence of probability measures to be the sequence of distributions of a martingale, a sub-martingale, or of partial sums of independent random variables.
In his Habilitationsschrift Almost Sure Behavior of Sums of Independent Random Variables and Martingales, Strassen refined and extended his previous work.
In 1969, Strassen began his work on the invention of algorithms and lower complexity bounds with the paper Gaussian Elimination is Not Optimal. In this paper, he introduced what is now known as Strassen's algorithm, an algorithm for performing the multiplication of large matrices much faster than the naive O(n³) time bound. In the same paper, he also presented an asymptotically fast algorithm for matrix inversion, based on the fast matrix multiplication method. This result was a significant theoretical breakthrough, spurring further research into fast matrix multiplication. Despite later theoretical improvements, Strassen’s algorithm remains a practical method for multiplying dense matrices of moderate to large sizes.
In 1971, Strassen co-authored a paper with Arnold Schönhage on the fast multiplication of large integers. The Schönhage–Strassen algorithm remained the fastest such algorithm for multiple decades, and is still used for many practical applications.
In 1973, Huber and Strassen collaborated on the paper Minimax Tests and the Neyman–Pearson Lemma for Capacities, which, in Huber’s subsequent work, became foundational to the field of robust statistics.
At the International Congress of Mathematicians in Vancouver in 1974, Strassen presented the paper Some Results in Algebraic Complexity Theory, where he introduced nonlinear lower bounds for the algebraic complexity of several important computational problems. He continued this line of work in the 1976 paper Computational Complexity over Finite Fields.
In 1977, Strassen collaborated with Robert M. Solovay on the Solovay–Strassen primality test, the first method to demonstrate that primality testing can be done in randomized polynomial time.
In the 1980 paper Some Polynomials That Are Hard to Compute, Strassen and Joachim von zur Gathen—using results of Joos Heintz and Malte Sieveking—showed that certain quite interesting univariate polynomials with rational coefficients are computationally hard to evaluate.
In 1983, Walter Baur and Strassen proved an inequality that essentially bounds the complexity of a single rational function in an arbitrary number of indeterminates from below by the complexity of the function together with all of its first-order derivatives. This extended the lower bounds of Strassen's 1974 paper to individual rational functions. Among the many applications, there is also a proof that computing the inverse of a matrix is not much harder than computing the determinant of that matrix.
In 1990, Strassen wrote a survey on Algebraic Complexity Theory.
At the first European Congress of Mathematics in Paris (1992), Strassen presented his work on the asymptotic spectrum of sets of bilinear maps, documented in the paper Algebra and Complexity.
Strassen's pioneering work contributed to probability theory, functional analysis, mathematical statistics, algorithm design, and computational complexity theory.
Awards and honors
[edit]In 1999 Strassen was awarded the Cantor medal,[2] and in 2003 he was co-recipient of the Paris Kanellakis Award with Robert Solovay, Gary Miller, and Michael Rabin for their work on randomized primality testing.[4] In 2008 he was awarded the Knuth Prize for "seminal and influential contributions to the design and analysis of efficient algorithms."[5] In 2011 he won the Konrad Zuse Medal of the Gesellschaft für Informatik.[3][7] Strassen also became a member of several leading german scientific academies, as well as a fellow of the American Mathematical Society.
References
[edit]- ^ FB Mathematik and Statistik Archived 2008-12-25 at the Wayback Machine, U. Konstanz.
- ^ a b c d e Schönhage, A. (2000), "Cantor-Medaille für Volker Strassen" (PDF), Jahresbericht der Deutschen Mathematiker-Vereinigung, 102 (4).
- ^ a b Winter, Cornelia (September 28, 2011), "Konrad-Zuse-Medaille für Informatik an Fritz-Rudolf Güntsch und Volker Strassen", Informationsdienst Wissenschaft (in German).
- ^ a b c Preis für Prof. Volker Strassen, uni'kon 16.2004, Univ. of Konstanz.
- ^ a b The 2008 Knuth Prize is awarded to Volker Strassen for his seminal and influential contributions to efficient algorithms, ACM SIGACT.
- ^ Volker Strassen at the Mathematics Genealogy Project
- ^ Konrad-Zuse-Medaille Archived 2014-08-19 at the Wayback Machine, Gesellschaft für Informatik (in German), retrieved 2012-03-09.
External links
[edit]- Home page of Dr. Volker Strassen
- Weisstein, Eric W. "Strassen Formulas". MathWorld. Formulas for fast(er) matrix multiplication and inversion.
- O'Connor, John J.; Robertson, Edmund F., "Volker Strassen", MacTutor History of Mathematics Archive, University of St Andrews
- 1936 births
- Living people
- 20th-century German mathematicians
- 21st-century German mathematicians
- German theoretical computer scientists
- Linear algebraists
- University of Göttingen alumni
- University of California, Berkeley faculty
- Academic staff of the University of Zurich
- Academic staff of the University of Konstanz
- Knuth Prize laureates
- Fellows of the American Mathematical Society