View source for Volker Strassen

{{Short description|German mathematician and algorithms researcher (b.1936)}}
{{Infobox scientist
| name              = Volker Strassen
| image             = Strassen Knuth Prize lecture.jpg <!--(filename only, i.e. without "File:" prefix)-->
| image_upright     = .75
| alt               = 
| caption           = Volker Strassen giving the Knuth Prize lecture at SODA 2009
| birth_date        = {{birth date and age |1936|4|29|mf=y}}
| birth_place       = [[Düsseldorf-Gerresheim]], [[Nazi Germany|Germany]]
| death_date        = <!--{{death date and age |YYYY|MM|DD |YYYY|MM|DD}} (death date then birth date)-->
| death_place       = 
| nationality       = [[Germany|German]]
| fields            = [[Mathematics]], [[Statistics]], [[Computer Science]]
| alma_mater        = [[University of Göttingen]]
| doctoral_advisor  = {{Interlanguage link multi|Konrad Jacobs|de}} <!--(or  | doctoral_advisors = )-->
| doctoral_students = [[Walter Baur]]<br>[[Peter Bürgisser]]<br>[[Joachim von zur Gathen]]<br>[[Joos Ulrich Heintz]]

| awards            = 
}}

'''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]].<ref>[http://www.math.uni-konstanz.de/fb_seiten/contrib/personen/personen.php?menu_var=Personen FB Mathematik and Statistik] {{webarchive|url=https://web.archive.org/web/20081225232139/http://www.math.uni-konstanz.de/fb_seiten/contrib/personen/personen.php?menu_var=Personen |date=2008-12-25 }}, U. Konstanz.</ref>

For important contributions to the [[analysis of algorithms]] he has received many awards, including the [[Cantor medal]],<ref name="cm"/> the [[Konrad Zuse Medal]],<ref name=IDW /> the [[Paris Kanellakis Award]] for work on [[Solovay–Strassen primality test|randomized primality testing]],<ref name="pfvs"/> the [[Knuth Prize]] for "seminal and influential contributions to the design and analysis of efficient algorithms."<ref name=sigact2008 />

==Biography==
[[File:VStrassen 19791026 340.jpg|left|thumb|upright|Strassen in 1979]]
Strassen was born on April 29, 1936, in [[Düsseldorf-Gerresheim]].<ref name="cm">{{citation|title=Cantor-Medaille für Volker Strassen|first=A.|last=Schönhage|authorlink=Arnold Schönhage|journal=Jahresbericht der Deutschen Mathematiker-Vereinigung|volume=102|issue=4|year=2000|url=http://dml.math.uni-bielefeld.de/JB_DMV/JB_DMV_102_4.pdf}}.</ref> After studying music, philosophy, physics, and mathematics at several German universities,<ref name="cm" /> he received his Ph.D. in mathematics in 1962 from the [[University of Göttingen]] under the supervision of {{Interlanguage link multi|Konrad Jacobs|de}}.<ref>{{MathGenealogy|id=36095}}</ref> 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 for Applied Mathematics|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.<ref name="cm"/> He retired in 1998.<ref name="pfvs">Preis für Prof. Volker Strassen, [http://www.ub.uni-konstanz.de/kops/volltexte/2008/6330/pdf/UniKon_16_04.pdf uni'kon 16.2004], Univ. of Konstanz.</ref>

==Research (selected papers)==
Strassen began his research as a [[probability theory|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 (probability theory)|martingale]], a sub-martingale, or of partial sums of independent [[random variable]]s.

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 [[algorithm]]s and [[computational complexity theory|lower complexity bounds]] with the paper ''Gaussian Elimination is Not Optimal''. In this paper, he introduced what is now known as [[Strassen algorithm|Strassen's algorithm]], an algorithm for performing the [[matrix multiplication|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, [[Peter J. Huber|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==
In 1999 Strassen was awarded the [[Cantor medal]],<ref name="cm"/> and in 2003 he was co-recipient of the [[Paris Kanellakis Award]] with [[Robert M. Solovay|Robert Solovay]], [[Gary Miller (professor)|Gary Miller]], and [[Michael O. Rabin|Michael Rabin]] for their work on randomized primality testing.<ref name="pfvs"/> In 2008 he was awarded the [[Knuth Prize]] for "seminal and influential contributions to the design and analysis of efficient algorithms."<ref name=sigact2008>[http://www.sigact.org/Prizes/Knuth/2008.html The 2008 Knuth Prize is awarded to Volker Strassen for his seminal and influential contributions to efficient algorithms] {{Webarchive|url=https://web.archive.org/web/20160514024808/http://www.sigact.org/Prizes/Knuth/2008.html |date=2016-05-14 }}, ACM SIGACT.</ref> In 2011 he won the [[Konrad Zuse Medal]] of the [[Gesellschaft für Informatik]].<ref name=IDW>{{citation|url=http://www.idw-online.de/pages/de/news443079|journal=Informationsdienst Wissenschaft|date=September 28, 2011|title=Konrad-Zuse-Medaille für Informatik an Fritz-Rudolf Güntsch und Volker Strassen|first=Cornelia|last=Winter|language=German}}.</ref><ref name=KZM>[http://www.gi.de/?id=276 Konrad-Zuse-Medaille] {{Webarchive|url=https://web.archive.org/web/20140819084001/http://www.gi.de/?id=276 |date=2014-08-19 }}, [[Gesellschaft für Informatik]] (in German), retrieved 2012-03-09.</ref>
Strassen also became a member of several leading german scientific academies, as well as a fellow of the American Mathematical Society.

==References==
{{reflist}}

==External links==
* [http://www.math.uni-konstanz.de/~strassen/ Home page of Dr. Volker Strassen]
* {{mathworld|urlname=StrassenFormulas|title=Strassen Formulas}} Formulas for fast(er) matrix multiplication and inversion.
* {{MacTutor Biography|id=Strassen}}

{{Kanellakis Award laureates}}
{{Knuth Prize laureates}}
{{Authority control}}

{{DEFAULTSORT:Strassen, Volker}}
[[Category:1936 births]]
[[Category:Living people]]
[[Category:20th-century German mathematicians]]
[[Category:21st-century German mathematicians]]
[[Category:German theoretical computer scientists]]
[[Category:Linear algebraists]]
[[Category:University of Göttingen alumni]]
[[Category:University of California, Berkeley faculty]]
[[Category:Academic staff of the University of Zurich]]
[[Category:Academic staff of the University of Konstanz]]
[[Category:Knuth Prize laureates]]
[[Category:Fellows of the American Mathematical Society]]