Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
Reading time: 20 minutes
Volker Strassen is a Computer Scientist and Mathematician who is best known as the person who broke the strongly held belief that Matrix Multiplication cannot be done faster than O(N^3) time. Yes, he is the man who changed the Matrix Multiplication game just like Einstein changed the Gravity game.
Just before 1970, it was strongly believed that Matrix Multiplication cannot be done faster than O(N^3) time complexity. Several attempts were made but neither a faster algorithm or a proof was formulated. The major breakthough came from Volker when he introduced his algorithm Strassen's matrix multiplication which broke the barrier and solved Matrix Multiplication in O(N^2.8) time complexity.
Volker Strassen, the man who changed the Matrix Multiplication game
This happens to be a major progress as it opened up a new path in field which was thought to be saturated. Though more optimized algorithms has been formulated now but this is considered as one of the strongest game changing theoretical results in the History of Algorithms.
Volker, once, said: "I have always been more intrigued by lower complexity bounds than by algorithms"
Major contributions of Volker Strassen were:
- Strassen's matrix multiplication
- Solovay Strassen primality test
- Schonhage Strassen algorithm (Fast Integer Multiplication)
Major awards presented to Volker Strassen were:
| Award | Year |
|---|---|
| Cantor medal | 1999 |
| Paris Kanellakis Award | 2003 |
| Knuth Prize | 2008 |
| Konrad Zuse Medal | 2011 |
| Fellow of American Mathematical Society | 2012 |
Background
Volker was born on 29th April, 1936 and currently (as of January 2020) lives in Germany.
He received a PhD in Mathematics in 1962 at University of Göttingen. Following this, he took a teaching position at the University of California, Berkeley (UC Berkeley). Soon he moved to University of Erlangen-Nuremberg as habilitation (self focused teaching and research). In 1968, he moved to Institute of Applied Mathematics at the University of Zurich and in 1988, he joined University of Konstanz. Finally, he retired in 1998.
| Affiliation | Starting Year |
|---|---|
| University of Göttingen | 1962 (completed) |
| University of California, Berkeley | 1962 |
| University of Erlangen-Nuremberg | 1962 |
| University of Zurich | 1968 |
| University of Konstanz | 1988 |
| Retired | 1998 |
Story: Bet with Ernst Specker
During Winter of 1974, Volker attended Oberwolfach Conference on Computational Complexity. A couple of months back, Volker formulated "A Fast Monte Carlo Test for Primality" which he had submitted it to SIAM Journal on Computing. He was discussing this with other attendents.
During the discussion, he said that a fast deterministic test for primality testing will be found in 10 years and a proof will be published that the set of primes is polynomially decidable.
This was a bold statement as it represented a major computation hurdle. His friend Ernst Specker (also a great Mathematician) disagreed and made a bet which was written in the Oberwolfach conference book.
10 years passed. Though progress was made in this field but the ultimate result as claimed by Volker was not established. Volker lost his bet and took Specker and his family on a Baloon ride around Zurich Lake. He, also, gifted one ounc of gold as was the terms of the bet.
The funny thing is that Specker brought one ounc of gold immediately after the bet (10 years ago) to be safe. In fact, the price of gold more than doubled in that 10 years.
Agrawal, Kayal and Saxena did finally solve this but in 2002. Volker was right but was off by 18 years.
Strassen's matrix multiplication
This can be considered as the single most important theoretical discovery in the field of Algorithms. It was strongly believed that Matrix Multiplication cannot be done better than O(N^3) time but it was Strassen who came up with his algorithm which broke the barrier and opened a whole new path.
He introduced this in his paper named "Gaussian Elimination" where he, also, introduced a fast algorithm for Matrix Inversion based on the same principles.
Solovay Strassen primality test
This is the first algorithm to show that primality test can be done in randomized polynomial time. He was a strong believer that primality testing can be done in polynomial time even though other prominent Mathematician disagreed.
This has, also, one of the first algorithms to demonstrate the use and power of Random Algorithms.
Schonhage Strassen algorithm
This is a fast Integer Multiplication algorithm developed by Volker along with Arnold Schonhage. It has been the fastest Integer multiplication algorithm from 1971 to 2007 (36 years).
It used recursive Fast Fourier Transform and other Number Theory ideas. The time complexity is O(N logN loglogN) for the multiplication of two N digit numbers.
It was beaten on 2007 by Furer's Algorithm which has a better asymptotic time complexity and is expected to work faster for astronomically large integers. It is not used in practice as of now and the use of Schonhage Strassen algorithm continues.
Quotes by Voker Strassen
Some quotes by Volker Strassen are:
"I have always been more intrigued by lower complexity bounds than by algorithms"
"Once you have a bike with pedals on the front wheel, you can increase its speed by expanding the wheel"
Poem by Volker Strassen (presented at a conference) for the birthday of his friend "Joachim":
"A jolly professor at b-it,
Brilliant scientist, teacher and wit,
Wrote his thesis out of reach
Studying curves on the beach;
The fresh air, said he, kept himself fit."
Volker Strassen is a great man as well as a great mathematician. He brought humanity's focus on cutting edge algorithms and how random algorithms should be taken seriously. Hope you got an insight into his mind.
