Fact-checked by Grok 2 weeks ago

Volker Strassen

Volker Strassen (born April 29, 1936) is a German mathematician renowned for his pioneering work in computational complexity theory, algebraic algorithms, and probabilistic methods in number theory.^[1] His most influential contributions include the development of Strassen's algorithm for fast matrix multiplication in 1969, which demonstrated that multiplying two n × n matrices could be done using fewer than the conventional 2n³ arithmetic operations, achieving a complexity of O(n^2.807), and the co-invention of the Schönhage–Strassen algorithm in 1971 for multiplying large integers in O(n log n log log n) time, which remained the fastest known method for decades.^[2] Additionally, Strassen co-developed the Solovay–Strassen primality test in 1977, a randomized Monte Carlo algorithm that efficiently verifies whether a number is prime with high probability, laying groundwork for modern cryptographic applications. Strassen's early career was marked by interdisciplinary interests; after studying music and philosophy at the University of Cologne in 1955, he shifted to mathematics at the Universities of Freiburg, Munich, and Göttingen, earning his diploma in 1961 and PhD in 1962 under Konrad Jacobs for his thesis on measurement errors and information theory.^[1] He held positions at the University of California, Berkeley (1962–1966), where he advanced to associate professor in statistics, followed by habilitation at the University of Erlangen in 1966, a professorship at the University of Zurich from 1968 to 1988, and finally at the University of Konstanz from 1988 until his retirement in 1998.^[1] Throughout his career, Strassen's research spanned probability theory—where he proved a law of the iterated logarithm for empirical distribution functions in 1964—functional analysis, robust statistics, and algebraic complexity, influencing fields from quantum physics foundations to asymptotic analysis of bilinear maps.^[1]^[3] Strassen's innovations have profoundly shaped algorithm design and theoretical computer science, earning him prestigious honors including the Cantor Medal from the German Mathematical Society in 1999 for his algebraic complexity contributions, the 2003 ACM Paris Kanellakis Theory and Practice Award shared with collaborators for the Solovay–Strassen test, and the 2008 Knuth Prize from ACM SIGACT for his seminal work on efficient algorithms.^[4]^[5] He was elected to the German National Academy of Sciences Leopoldina in 1992 and received the Konrad Zuse Medal in 2011.^[3]^[6]

Early Life and Education

Childhood and Early Studies

Volker Strassen was born on April 29, 1936, in Gerresheim, a borough of Düsseldorf, Germany.^[1] Little is documented about Strassen's family background or specific influences on his early intellectual development, though he grew up in post-war Germany during a period of reconstruction that shaped many of his generation. He attended the Gerresheim Gymnasium, where he specialized in modern languages and graduated in 1955, reflecting an initial orientation toward the humanities.^[1] In 1955, Strassen began his university studies at the University of Cologne, focusing on music and philosophy, fields that aligned with his early artistic interests. He subsequently spent brief periods at the University of Freiburg and the University of Munich, where he transitioned to mathematics and physics as his primary areas of study.^[1] This shift marked a pivotal change toward the sciences, setting the stage for his later formal education at the University of Göttingen.^[1]

Formal Education and Thesis

Volker Strassen began his formal studies in mathematics and physics at the University of Cologne in 1955, initially alongside interests in music and philosophy, before focusing on the sciences; he continued this coursework at the Universities of Freiburg and Munich.^[1] In 1959, he transferred to the University of Göttingen, where he completed his Diploma in Mathematics in 1961 under the guidance of faculty specializing in probability and analysis.^[1] Strassen pursued his doctoral studies at Göttingen, earning his PhD on May 11, 1962, supervised by Konrad Jacobs, a prominent figure in ergodic theory.^[7] His thesis, titled Messfehler und Information (Measurement Errors and Information), was later published in the Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete. The work examined the interplay between observational errors in measurements and the transmission of information in probabilistic systems, drawing on foundational ideas from physics and statistics during his undergraduate preparation.^[1] The thesis contributed to early developments in information theory by analyzing how measurement inaccuracies affect the reliability of probabilistic inferences, including asymptotic estimates related to Shannon's entropy concepts.^[1] Strassen's approach integrated error models from physics with information-theoretic bounds, providing a framework for quantifying uncertainty in data collection processes within stochastic contexts. This foundational exploration highlighted the limitations of precise measurements in noisy environments, influencing subsequent work on robust statistical methods.^[8]

Academic Career

Initial Positions in the United States

Following his PhD from the University of Göttingen in 1962, Volker Strassen moved to the United States and took up an appointment as an Assistant Professor in the Department of Statistics at the University of California, Berkeley.^[1] This position marked his entry into the American academic system.^[1] Strassen served at Berkeley from 1962 until 1968, during which time he was promoted to Associate Professor, reflecting his growing reputation in probability.^[1] A notable experience in this period was his participation in the Fifth Berkeley Symposium on Mathematical Statistics and Probability held in 1965–1966, where he delivered a presentation on the almost sure behavior of sums of independent random variables and martingales, fostering interactions with leading statisticians and probabilists.^[1] Amid his Berkeley tenure, Strassen achieved a significant milestone by completing his Habilitation in 1966 at the University of Erlangen, under the supervision of Konrad Jacobs, qualifying him for a full professorship in Germany.^[1]

European Professorships and Retirement

In 1968, Volker Strassen was appointed full professor at the Institute of Applied Mathematics at the University of Zurich, where he served for twenty years until 1988.^[1] During this period, he directed the institute, fostering advancements in applied mathematics and algorithmic research. His tenure at Zurich solidified his reputation as a leading figure in European academia, emphasizing interdisciplinary approaches to computational problems. In 1988, Strassen relocated to Germany, accepting a full professorship in the Department of Mathematics and Statistics at the University of Konstanz, a role he maintained until his retirement in 1998.^[1] At Konstanz, he contributed to departmental leadership by supervising numerous doctoral students and representing the department in international scientific bodies, including as a member of the German National Academy of Sciences Leopoldina on behalf of mathematics and statistics.^[9] Following his retirement, Strassen was conferred professor emeritus status at the University of Konstanz, enabling continued scholarly engagement with the institution.^[10] His emeritus affiliation persisted at least until 2001, reflecting his enduring impact on the department.^[10]

Research Contributions

Work in Probability Theory

Volker Strassen's early research in probability theory focused on limit theorems and the asymptotic behavior of stochastic processes, laying foundational results that bridged discrete and continuous probability models. His PhD thesis, titled Messfehler und Information (Measurement Errors and Information), completed in 1962 at the University of Göttingen under Konrad Jacobs, examined probabilistic models for measurement errors and their implications for information extraction in statistical settings.^[1] This work connected error analysis in observations to information-theoretic bounds, influencing early developments in robust statistical inference by quantifying uncertainty in probabilistic measurements.^[1] A cornerstone of Strassen's contributions is his 1964 paper, "An Invariance Principle for the Law of the Iterated Logarithm," which established what is now known as Strassen's law.^[11] Consider a sequence of independent and identically distributed random variables X_1, X_2, \dots with mean 0 and variance 1, and let S_n = \sum_{i=1}^n X_i denote the partial sums. Strassen proved that, almost surely,

\limsup_{n \to \infty} \sup_{0 \leq t \leq 1} \frac{S_{\lfloor nt \rfloor}}{\sqrt{2n \log \log n}} = 1,

and moreover, the set of scaled paths \left\{ \frac{S_{\lfloor nt \rfloor}}{\sqrt{2n \log \log n}} : 0 \leq t \leq 1 \right\} is dense in the unit ball of the space C[0,1] of continuous functions on [0,1] equipped with the supremum norm.^[11] This functional form of the law of the iterated logarithm provides a strong invariance principle, approximating the discrete partial sum process by paths of Brownian motion and revealing the fine-scale fluctuations of random walks.^[1] The result implies that the normalized sums explore the entire boundary of the limiting set almost surely, offering precise control over the almost sure behavior of stochastic processes in the central limit regime.^[11] Strassen's law has profound implications for stochastic processes, enabling the transfer of properties from continuous Gaussian processes like Brownian motion to discrete sums, which facilitates proofs of limit theorems via embedding techniques.^[12] In mathematical statistics, it underpins invariance principles for empirical processes and strong approximations, such as those in the Kolmogorov-Smirnov statistic, by establishing almost sure convergence to universal limiting objects.^[1] For instance, it supports the analysis of maximal deviations in sample paths, impacting areas like sequential analysis and non-parametric inference.^[13] Building on this, Strassen's 1965 paper, "Almost Sure Behavior of Sums of Independent Random Variables and Martingales," extended these ideas to martingale sequences, deriving almost sure bounds on their growth and fluctuations analogous to the iterated logarithm.^[14] Presented at the Fifth Berkeley Symposium on Mathematical Statistics and Probability, this work generalized the 1964 invariance principle to dependent increments, broadening its applicability to filtered probability spaces.^[15] Another key 1960s contribution, "The Existence of Probability Measures with Given Marginals" (1965), addressed the construction of joint distributions compatible with specified marginals, providing criteria for the existence of couplings in multivariate probability and influencing optimal transport theory. These early papers collectively advanced invariance principles in limit theorems, shaping modern probabilistic methods for handling dependence and marginal constraints in statistics.^[1]

Developments in Algebraic Complexity

Volker Strassen is widely regarded as the founding father of algebraic complexity theory, a field that analyzes the computational resources required for algebraic computations using models inspired by algebraic geometry and circuit theory. His pioneering efforts established foundational concepts, including the study of arithmetic circuits, which model the computation of multivariate polynomials through directed acyclic graphs with gates for addition, multiplication, and constants. Strassen's introduction of bilinear complexity and tensor rank provided rigorous tools to measure the minimal number of multiplications needed for bilinear maps, such as matrix multiplication, thereby bridging abstract algebraic structures with practical computational limits.^[16]^[17]^[1] In 1969, Strassen's seminal paper demonstrated that the standard implementation of Gaussian elimination is not optimal for solving systems of linear equations, showing that fewer multiplications are possible with more additions by counting arithmetic operations separately for multiplications and additions. This work highlighted the need to distinguish between different types of operations in evaluating the efficiency of classical methods. By formalizing these measures, Strassen laid the groundwork for evaluating algebraic algorithms beyond traditional numerical analysis, emphasizing asymptotic behavior over exact counts.^[18] Strassen further advanced the field by developing theoretical models and bounds for the computational complexity of algebraic problems, notably introducing the \omega notation to denote the infimum of exponents k such that n \times n matrix multiplication can be performed in O(n^k) time. His analysis connected circuit size and depth to algebraic varieties, providing degree bounds that link polynomial degree to computational resources via algebraic geometry. These models enabled the classification of problems in terms of their minimal circuit complexity, influencing how researchers approach hardness proofs for algebraic tasks like determinant computation and polynomial evaluation.^[16]^[19] Strassen's ideas profoundly shaped subsequent research in theoretical computer science, inspiring the development of Valiant's algebraic complexity classes VP and VNP, which analogize P and NP for arithmetic circuits. His frameworks facilitated breakthroughs in lower bound techniques, such as the laser method for improving \omega bounds, and influenced geometric complexity theory aimed at separating these classes. The integration of his concepts into broader complexity theory has sustained active investigation into the limits of algebraic computation, with applications extending to cryptography and quantum algorithms.^[5]^[17]^[20]

Key Algorithms and Applications

Volker Strassen's seminal contribution to matrix multiplication, introduced in 1969, revolutionized computational complexity by demonstrating that the standard cubic-time algorithm is not optimal. For two $2 \times 2 matrices A = \begin{pmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{pmatrix} and B = \begin{pmatrix} b_{11} & b_{12} \\ b_{21} & b_{22} \end{pmatrix}, the classical method requires 8 scalar multiplications, but Strassen's approach reduces this to 7 through a clever decomposition into subproblems. The algorithm recursively partitions larger n \times n matrices (assuming n is a power of 2) into four n/2 \times n/2 blocks and computes the products via the following seven multiplications:

\begin{align*} M_1 &= (a_{11} + a_{22})(b_{11} + b_{22}), \\ M_2 &= (a_{21} + a_{22}) b_{11}, \\ M_3 &= a_{11} (b_{12} - b_{22}), \\ M_4 &= a_{22} (b_{21} - b_{11}), \\ M_5 &= (a_{11} + a_{12}) b_{22}, \\ M_6 &= (a_{21} - a_{11}) (b_{11} + b_{12}), \\ M_7 &= (a_{12} - a_{22}) (b_{21} + b_{22}). \end{align*}

These are combined with 18 additions and subtractions to yield the result, achieving an asymptotic complexity of O(n^{\log_2 7}), where \log_2 7 \approx 2.807, compared to the classical O(n^3). This exponent has since been improved through subsequent research, reaching approximately 2.371 as of 2024.^[21] This improvement, grounded in algebraic complexity theory, has applications in specialized high-performance computing and integer arithmetic libraries, though adoption in standard numerical libraries is limited due to constants and stability issues.^[22]^[23] In collaboration with Robert Solovay, Strassen developed a probabilistic primality test in 1977 that marked a breakthrough in number-theoretic algorithms. The Solovay-Strassen test determines whether an odd integer n > 2 is probably prime by selecting a random base a with $1 < a < n and verifying if the Jacobi symbol (a/n) equals a^{(n-1)/2} \mod n, a condition derived from Euler's criterion generalized via the properties of quadratic residues. If the equality fails for any a, n is composite; if it holds for multiple independent trials, n is deemed probably prime with an error probability at most $1/2 per trial, reducible to $2^{-k} after k iterations. This randomized method, requiring O(\log^3 n) time per trial using fast exponentiation, has been instrumental in cryptography, facilitating efficient key generation for RSA by quickly identifying probable primes up to thousands of bits without deterministic guarantees.^[24] Strassen's work with Arnold Schönhage in 1971 yielded an asymptotically superior algorithm for multiplying large integers, leveraging the fast Fourier transform (FFT) over rings of integers modulo powers of 2. The Schönhage-Strassen algorithm multiplies two n-bit integers by representing them in a digit set of base $2^m (with m = \lceil \log_2 n \rceil + 1), applying FFT for convolution, and recovering the product via integer arithmetic, achieving a time complexity of O(n \log n \log \log n). This held the record for the fastest integer multiplication until 2007, when it was surpassed by Fürer's algorithm, and remains influential in modern arbitrary-precision arithmetic libraries such as GMP, where it underpins operations for numbers with millions of digits in computational number theory and high-precision simulations.^[25]

Recognition and Legacy

Major Awards

In 1992, Strassen was elected to the German National Academy of Sciences Leopoldina.^[3] In 1999, Volker Strassen received the Georg Cantor Medal from the Deutsche Mathematiker-Vereinigung for his lifetime achievements in mathematics, recognizing his foundational contributions to the theory of algorithms and computational complexity.^[4]^[1] Strassen shared the 2003 ACM Paris Kanellakis Theory and Practice Award with Gary L. Miller, Michael O. Rabin, and Robert M. Solovay for their development of the Solovay-Strassen primality test and subsequent advances in primality testing and probabilistic algorithms, which have significantly influenced cryptography and computational number theory.^[26] The 2008 Knuth Prize, awarded by ACM SIGACT and the IEEE Computer Society's Technical Committee on the Mathematical Foundations of Computing, was given to Strassen for his seminal contributions to efficient algorithms, particularly his fast matrix multiplication algorithm and work on probabilistic primality testing that have profoundly shaped both theoretical and practical computing.^[5] In 2011, Strassen was honored with the Konrad Zuse Medal from the Gesellschaft für Informatik for his pioneering role in algorithmics, including groundbreaking algorithms for fundamental arithmetic problems such as matrix multiplication that remain in practical use today.^[27]

Invited Lectures and Influence

Volker Strassen delivered an invited lecture at the 1966 International Congress of Mathematicians (ICM) in Moscow, where he presented on probability theory and statistics, highlighting his early work on the law of the iterated logarithm.^[28] Eight years later, at the 1974 ICM in Vancouver, Strassen was again an invited speaker, this time in the section on discrete mathematics and theory of computation, discussing advancements in algebraic complexity.^[28] His prominence continued with an invited address on "Algebra and Complexity" at the First European Congress of Mathematics in Paris in 1992.^[1] More recently, Strassen gave an invited talk on the asymptotic spectrum and matrix multiplication at the 2012 International Symposium on Symbolic and Algebraic Computation (ISSAC).^[29] As a mentor, Strassen supervised nine PhD students, including notable figures such as Peter Bürgisser, who advanced algebraic complexity and its intersections with quantum computing; Joachim von zur Gathen, known for contributions to algebraic algorithms; and Joos Heintz, whose work spans computational algebraic geometry.^[30] These students, along with over 100 academic descendants, have extended Strassen's ideas into diverse areas of theoretical computer science.^[30] Strassen also collaborated extensively, fostering interdisciplinary ties, and his son, Tyko Strassen, has pursued a career in mathematics with interests overlapping his father's in complexity and algebra.^[1] Strassen's legacy as the founding father of algebraic complexity theory has profoundly shaped the field, providing foundational frameworks for analyzing computational problems over algebraic structures.^[1] His innovations, such as efficient algorithms for matrix operations and integer multiplication, have influenced randomized algorithms by enabling faster probabilistic computations in linear algebra.^[1] These contributions are now integral to computer science curricula, appearing in standard algorithms textbooks as exemplars of sub-cubic time complexity.^[1] In software, Strassen's methods underpin high-performance libraries for numerical analysis, while his fast multiplication techniques support cryptographic protocols reliant on large-integer arithmetic.^[1]

References

[1]
Volker Strassen (1936 - ) - Biography - University of St Andrews
Strassen was awarded his Diploma in Mathematics from Göttingen in 1961 and his doctorate in the following year for his thesis Messfehler und Information Ⓣ. ( ...
[2]
https://doi.org/10.1007/BF02165411
[3]
Volker Strassen - List of Members
Volker Strassen has worked in different fields of mathematics, mathematical statistics and theoretical computer science at the universities of Göttingen ...
[4]
Cantor - Deutsche Mathematiker-Vereinigung
Volker Strassen. Die Deutsche Mathematiker-Vereinigung verleiht unter der Präsidentschaft von Karl-Heinz Hoffmann die Cantor-Medaille an Professor Dr. Volker ...Missing: Medal | Show results with:Medal
[5]
2008
The 2008 Knuth Prize is awarded to Volker Strassen for his seminal and influential contributions to efficient algorithms. Volker Strassen's work has had ...
[6]
Volker Strassen - dblp
Jun 8, 2025 · List of computer science publications by Volker Strassen.Missing: Basel | Show results with:Basel
[7]
Konrad Jacobs (1928–2015) | Jahresbericht der Deutschen ...
Feb 10, 2017 · Konrad Jacobs was born on August 24, 1928, in Rostock. His parents, Werner and Waldtraut Jacobs, were both doctoral students of the zoologist ...Missing: education Freiberg
[8]
the 1972 wald lecture robust statistics: a review"2 - jstor
STRASSEN, V. (1964). Messfehler und Information. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 2 273-305. "STUDENT" (1927). Errors of routine analysis ...
[9]
Volker Strassen - Wikipedia
Volker Strassen (born April 29, 1936) is a German mathematician, a professor emeritus in the department of mathematics and statistics at the University of ...Missing: Basel | Show results with:Basel
[10]
Memberships in the Leopoldina (German National Academy of ...
Professor Volker Strassen is a German mathematician and was a professor of mathematics at the University of Konstanz until 2001. He represents the ...
[11]
Memberships in the Heidelberg Academy of Sciences and Humanities
Professor Volker Strassen is a German mathematician and was a professor of mathematics at the University of Konstanz until 2001. He represents the ...
[12]
An invariance principle for the law of the iterated logarithm
Cite this article. Strassen, V. An invariance principle for the law of the iterated logarithm. Z. Wahrscheinlichkeitstheorie verw Gebiete 3, 211–226 (1964) ...
[13]
Some Strassen-Type Laws of the Iterated Logarithm ... - Project Euclid
"Some Strassen-Type Laws of the Iterated Logarithm for Multiparameter Stochastic Processes with Independent Increments." Ann. Probab. 1 (2) 272 - 296, April ...Missing: implications | Show results with:implications
[14]
STATISTICS - Project Euclid
The invariance principle for one-sample rank-order statistics. PRANAE KUMAR ... HUBER AND VoLKER STRAssEN 223. Vol. 2, No. 1—January 1974. 冕繼. Institute ...<|control11|><|separator|>
[15]
Volker Strassen: Persönliche Seiten
... Fifth Berkeley Symposium 1965/66, Vol. II, Part I, 315-343. The Existence of Probability Measures with Given Marginals, The Annals of Mathematical ...
[16]
Proceedings of the Fifth Berkeley Symposium on Mathematical ...
Volker Strassen. Berkeley Symposium on Mathematical Statistics and Probability Vol. 5.2A, 315-343 (1967). Open Access. KEYWORDS: 60.30. DOWNLOAD PDF. SAVE TO MY ...
[17]
Mathematics People
Strassen Awarded ACM Knuth. Prize. Volker Strassen of the University of Konstanz has been awarded the 2008 Knuth Prize of the Association for. Computing ...
[18]
ACM SIGACT 2008 Knuth Prize Recognizes Strassen for ...
For his work on primality testing and randomized algorithms Strassen was the co-recipient of the 2003 ACM Paris Kanellakis Theory and Practice Award. Modern ...
[19]
Gaussian Elimination is not Optimal. - EuDML
Gaussian Elimination is not Optimal. V. STRASSEN · Numerische Mathematik (1969). Volume: 13, page 354-356; ISSN: 0029-599X; 0945-3245/e ...
[20]
[PDF] geometry and the complexity of matrix multiplication
We survey results in algebraic complexity theory, focusing on matrix multiplication. ... Volker Strassen, Gaussian elimination is not optimal, Numer. Math ...
[21]
[PDF] Introduction to geometric complexity theory
May 31, 2025 · Abstract. Geometric complexity theory is an approach towards proving lower bounds in algebraic complexity theory via methods from algebraic ...Missing: influence | Show results with:influence
[22]
[PDF] Using Strassen's Algorithm to Accelerate the Solution of Linear ...
The use of Strassen's method potentially could speed up a number of linear equations and eigenvalue computations. In addition, complex routines in LAPACK could.
[23]
Using Strassen's matrix multiplication in high performance solution ...
Performance characteristics of dense and structured blocked linear system solvers are studied when Strassen's matrix multiplication is used in the update ...
[24]
[PDF] Notes on Primality Testing And Public Key Cryptography Part 1
Here is the Solovay–Strassen primality test. Solovay–Strassen test. The input is an odd integer n > 3. Page 142. 142. CHAPTER 6. THE SOLOVAY–STRASSEN TEST.
[25]
[PDF] A GMP-based implementation of Schönhage-Strassen's ... - Hal-Inria
Jan 25, 2007 · In this article we concentrate on the question of an optimized implementation of Schönhage-Strassen's algorithm on a classical workstation. In ...Missing: influence | Show results with:influence
[26]
Volker Strassen - ACM Awards
Randomized algorithms for testing whether a number is prime were introduced by Robert Solovay and Volker Strassen and by Michael Rabin.
[27]
Konrad-Zuse-Medaille - Gesellschaft für Informatik e.V.
Dr. Volker Strassen ist einer der Wegbereiter der Algorithmik. Er hat mehrere bahnbrechende Algorithmen für fundamentale Probleme der Arithmetik entwickelt, die ...
[28]
https://www.mathunion.org/icm-plenary-and-invited-speakers
[29]
ISSAC 2012 - Invited speakers
The conference features three invited talks by Frits Beukers, Marie-Francoise Roy and Volker Strassen. Frits Beukers, University of Utrecht, Netherlands ...Missing: Congress | Show results with:Congress
[30]
Volker Strassen - The Mathematics Genealogy Project
According to our current on-line database, Volker Strassen has 9 students and 100 descendants. We welcome any additional information. If you have additional ...