Volker Strassen

Quick Info

29 April 1936
Düsseldorf-Gerresheim, Germany

Volker Strassen is a German mathematiican who can be considered the founding father of algebraic complexity theory.


Volker Strassen was born in Gerresheim, one of the boroughs of the city of Düsseldorf, situated to the east of the main city. He studied at the Gerresheim Gymnasium, which specialised in modern languages, graduating from the high school in 1955. At this stage Strassen's interests were more on the arts side rather than science and he decided to study music and philosophy at university. He entered the University of Cologne in 1955 and began to take courses on music and philosophy. His undergraduate career was spent at a variety of different universities, for he moved to the University of Freiberg and then to the University of Munich. Not only was he moving between different universities, but his interests were changing too and he changed topics to take courses on mathematics and physics.

After taking courses at the Universities of Cologne, Freiberg and Munich, he went to the University of Göttingen to complete his training. There his studies were supervised by Konrad Jacobs who worked in ergodic theory. Jacobs, who had been an assistant at Munich before taking up the chair of mathematical statistics at Göttingen in 1959, had not previously been a thesis advisor so Strassen became his first student. 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 . Also in 1962 he attended the Third Prague Conference on Information Theory, Statistical Decision Functions and Random Processes where he gave the lecture Asymptotische Abschätzungen in Shannons Informationstheorie . This was published in the conference proceeding in 1964, the same year as his paper containing the main results from his doctoral thesis was published.

After the award of his doctorate, Strassen went to the University of California, Berkeley in the United States. Julia Robinson's sister, Constance Reid, describes meeting Strassen around this time [4]:-
Julia was auditing a class of Alfred Tarski's in which the person who always arranged to sit next to her was a young Ph.D. from Göttingen, a probabalist then, named Volker Strassen. She told him that her sister was planning to write a book about men and women of modern mathematics, and Volker said that of course then we must come to Göttingen and when we came he would show us around. ... Volker's Ph.D. adviser, Konrad Jacobs, was eager to entertain us - rather, to entertain Julia. It was clear that Volker had scored a coup with his "Doktorvater" by bringing her to Göttingen. ... Volker himself, whose wife was momentarily expecting their second child, told us that if the baby was a girl ... he was going to name her Julia. The baby was born while we were still in Göttingen but turned out to be a boy, so Volker named him Tyko after Tycho Brahe, which showed me the class Julia was in as far as Volker was concerned.
We note that Tyko Strassen is now a mathematician with similar interests to his father.

At Berkeley, Volker Strassen took up an appointment as an Assistant Professor in the Department of Statistics and was later promoted to Associate Professor there. Strassen wrote a highly influential paper in 1964, namely An Invariance Principle for the Law of the Iterated Logarithm. This paper contains what today is called 'Strassen's law of the iterated logarithm', showing scale invariance in random walks. The importance of the results was quickly realised and Strassen was invited to lecture at the International Congress of Mathematicians held in Moscow in 1966. His lecture Der Satz mit dem iterierten Logarithmus surveyed his results on the law of the iterated logarithm and discussed the relation of his work to that of others. A postdoctoral grant from the Deutschen Mathematiker-Vereinigung (German Mathematical Society) allowed Strassen to habilitate in 1966 at the University of Erlangen where Konrad Jacobs had moved in 1965 to set up a centre for probability with Hans Bauer who had moved there from Hamburg.

In 1968 Strassen took up an appointment at the Institute of Applied Mathematics at the University of Zürich. At around this time his interests changed somewhat and he began to study the performance of algorithms. In 1968 he made a major, and very surprising, discovery [2]:-
Perhaps the first real surprise in algorithm analysis occurred with Strassen's discovery in 1968 of a new method for multiplying two n×nn \times n matrices. While the classic algorithm we all learned in high school requires 2n3n22n^{3} - n^{2} scalar arithmetic operations, Strassen's algorithm uses fewer than 7nk6n27n^{k} - 6n^{2} operations, where k=log27=2.808k = \log_{2} 7 = 2.808. Therefore, this new algorithm uses fewer operations than the classic method when nn is greater than 654. Strassen's discovery touched off an intensive search for asymptotically better matrix multiplication algorithms.
Strassen spent twenty years at the University of Zürich during which time he made many more highly significant discoveries including, in 1977, his test for whether a number is prime using a randomised algorithm. We will quote from the citations of prestigious awards made to Strassen to give further details of his contributions. Before that, let us note that he left Zürich in 1988 to take up a position at the University of Konstanz. He retired in 1998.

In 1999 Strassen was awarded the Cantor medal by the Deutsche Mathematiker Vereinigung (German Mathematical Society). The citation reads [5]:-
The Society honours a great scientist who through his multifaceted contributions has given mathematical research decisive impulses and has opened up new areas. His work in probability theory, algebraic complexity theory, and theoretical computer science has been groundbreaking. Those results will always be linked to his name.
Strassen received the 2003 Association for Computing Machinery Paris Kanellakis Theory and Practice Award (jointly with Gary Miller, Michael Rabin, Robert Solovay). We give the following extract from the citation [3]:-
Randomized algorithms for testing whether a number is prime were introduced by Robert Solovay and Volker Strassen and by Michael Rabin. Each of these tests is based on an efficiently computable predicate depending on nn, the number being tested for primality, and an integer bb in the range [2,n][ 2, n]. In each case, the chosen predicate has the property that, if nn is prime, then the predicate must be true for all bb; therefore, a value bb for which the predicate is false is a witness to the compositeness of nn. Solovay and Strassen (1977) proved that, if nn is composite then, for their predicate, at least half the possible choices of bb are witnesses to its compositeness. ... The Solovay-Strassen and Miller-Rabin tests demonstrate the power of randomized algorithms and make it possible to generate large random prime numbers and thus construct candidate instances of the RSA cryptosystem. Essentially all cryptographic systems being considered today require the generation of large primes.
The Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory presented Strassen with the 2008 Knuth Prize at their 'Symposium on Discrete Algorithms' held in New York in January 2009. He received the award [1]:-
... for his contributions to the theory and practice of algorithm design. Strassen's innovations enabled fast and efficient computer algorithms, the sequence of instructions that tells a computer how to solve a particular problem. His discoveries resulted in some of the most important algorithms used today on millions if not billions of computers around the world, and fundamentally altered the field of cryptography, which uses secret codes to protect data from theft or alteration. ... Strassen's algorithms include fast matrix multiplication, integer multiplication, and a test for the primality of integers. The discovery of provably fast algorithms to determine whether a number is prime or composite profoundly changed the cryptography field. These primality tests are now performed billions of times a day on machines worldwide to apply cryptographic methods that make data secure. The primality test opened the world of probabilistic algorithms to theoretical computer scientists, presenting an innovative way to solve sharing problems, which are often used in fault tolerant systems. ... Modern primality tests involve multiplying many large integers together. For thirty five years, the Schonhage-Strassen integer multiplication method algorithm held the world record for the fastest multiplication algorithm. It is still a standard tool for computing with very large numbers. In 1969, Strassen discovered a novel way to multiply two matrices, a critical element of linear algebra that is pervasive throughout the sciences. It is an intricate yet simple algorithm that remains the method of choice for multiplying dense matrices of size 30 by 30 or more on machines today. Using this new matrix multiplication routine, Strassen was able to show that Gaussian elimination (an efficient algorithm for solving systems of linear equations) is not an optimal solution. Few students in computer science have not encountered Strassen's multiplication algorithm in their undergraduate program. Researchers in algorithm design have regularly used his method to improve the run time of their algorithms. In addition to his very practical work, Strassen has proved fundamental theorems in statistics, including "Strassen's law of the iterated logarithm" and the principle of strong invariance. He is considered the founding father of algebraic complexity theory with his work on the degree bound, connecting complexity to algebraic geometry. He also introduced fundamental notions and results in bilinear complexity and tensor rank.
We mentioned above that Strassen was an invited speaker at the International Congress of Mathematicians held in Moscow in 1966. He was also an invited speaker at the International Congress of Mathematicians held in Vancouver in 1974 when he spoke on Some results in algebraic complexity theory. At the International Congress of Mathematicians at Berkeley in 1986 the Nevanlinna Prize was awarded to Leslie Valiant and Strassen was invited to give a lecture explaining the significance of Valiant's work. This was not the only time that Strassen was involved with the presentation of the Nevanlinna Prize for he was on the committee that chose Alexander Razborov as the winner of the award at the International Congress of Mathematicians at Kyoto in 1990. Let us also mention that Strassen was an invited speaker at the First European Congress of Mathematics held in Paris in 1992 when he gave the lecture Algebra and complexity.

References (show)

  1. ACM SIGACT 2008 Knuth Prize recognizes Strassen for contributions to efficient algorithm design, Association for Computing Machinery. http://www.acm.org/press-room/news-releases-2008/knuth-prize-08/
  2. C C McGeoch, Experimental analysis of algorithms, Notices Amer. Math. Soc. 48 (3) (2001), 304-311.
  3. Paris Kanellakis Theory and Practice Award 2003, Association for Computing Machinery. http://awards.acm.org/citation.cfm?id=2857138&srt=all&aw=147&ao=KANELLAK
  4. C Reid, Being Julia Robinson's Sister, Notices Amer. Math. Soc. 43 (12) (1996), 1486-1492.
  5. Strassen Receives Cantor Medal, Notices Amer. Math. Soc. 47 (3) (2000), 374-375.
  6. Strassen Awarded ACM Knuth Prize, Notices Amer. Math. Soc. 56 (2) (2009), 268.

Additional Resources (show)

Honours (show)

Written by J J O'Connor and E F Robertson
Last Update February 2010