Volker Strassen (born April 29, 1936) is a German

mathematician A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems. Mathematicians are concerned with numbers, data, quantity, structure, space, models, and change. History On ...

, a professor emeritus in the department of mathematics and statistics at the

University of Konstanz The University of Konstanz (german: Universität Konstanz) is a university in the city of Konstanz in Baden-Württemberg, Germany. Its main campus was opened on the Gießberg in 1972 after being founded in 1966. The university is Germany's ...

. For important contributions to the

analysis of algorithms In computer science, the analysis of algorithms is the process of finding the computational complexity of algorithms—the amount of time, storage, or other resources needed to execute them. Usually, this involves determining a function that re ...

he has received many awards, including the

Cantor medal The Cantor medal of the Deutsche Mathematiker-Vereinigung is named in honor of Georg Cantor, the first president of the society. It is awarded at most every second year during the yearly meetings of the society. The prize winners are mathematician ...

, the

Konrad Zuse Medal The Konrad Zuse Medal for Services to Computer Science is the highest award of the (German Computer Science Society), given every two years to one or sometimes two leading German computer scientists. It is named after German computer pioneer Konra ...

, the

Paris Kanellakis Award The Paris Kanellakis Theory and Practice Award is granted yearly by the Association for Computing Machinery (ACM) to honor "specific theoretical accomplishments that have had a significant and demonstrable effect on the practice of computing". It wa ...

for work on randomized primality testing, the

Knuth Prize The Donald E. Knuth Prize is a prize for outstanding contributions to the foundations of computer science, named after the American computer scientist Donald E. Knuth. History The Knuth Prize has been awarded since 1996 and includes an award of US ...

for "seminal and influential contributions to the design and analysis of efficient algorithms."

Biography

Strassen was born on April 29, 1936, in

Düsseldorf-Gerresheim Gerresheim is one of the City of Düsseldorf, Germany's fifty quarters. Part of Borough 7, it is located in the eastern part of the municipality. Gerresheim is much older than Düsseldorf itself, having been an independent city with a rich histor ...

.. After studying music, philosophy, physics, and mathematics at several German universities, he received his Ph.D. in mathematics in 1962 from the

University of Göttingen The University of Göttingen, officially the Georg August University of Göttingen, (german: Georg-August-Universität Göttingen, known informally as Georgia Augusta) is a public research university in the city of Göttingen, Germany. Founded ...

under the supervision of . He then took a position in the department of

statistics Statistics (from German language, German: ''wikt:Statistik#German, Statistik'', "description of a State (polity), state, a country") is the discipline that concerns the collection, organization, analysis, interpretation, and presentation of ...

at the

University of California, Berkeley The University of California, Berkeley (UC Berkeley, Berkeley, Cal, or California) is a public land-grant research university in Berkeley, California. Established in 1868 as the University of California, it is the state's first land-grant u ...

while performing his

habilitation Habilitation is the highest university degree, or the procedure by which it is achieved, in many European countries. The candidate fulfills a university's set criteria of excellence in research, teaching and further education, usually including a ...

at the

University of Erlangen-Nuremberg A university () is an institution of higher (or tertiary) education and research which awards academic degrees in several academic disciplines. Universities typically offer both undergraduate and postgraduate programs. In the United States, t ...

, where Jacobs had since moved. In 1968, Strassen moved to the Institute of Applied Mathematics at the

University of Zurich The University of Zürich (UZH, german: Universität Zürich) is a public research university located in the city of Zürich, Switzerland. It is the largest university in Switzerland, with its 28,000 enrolled students. It was founded in 1833 f ...

, where he remained for twenty years before moving to the University of Konstanz in 1988. He retired in 1998.Preis für Prof. Volker Strassen
uni'kon 16.2004
Univ. of Konstanz.

Research

Strassen began his researches as a probabilist; his 1964 paper ''An Invariance Principle for the Law of the Iterated Logarithm'' defined a functional form of the

law of the iterated logarithm In probability theory, the law of the iterated logarithm describes the magnitude of the fluctuations of a random walk. The original statement of the law of the iterated logarithm is due to A. Ya. Khinchin (1924). Another statement was given by A ...

, showing a form of

scale invariance In physics, mathematics and statistics, scale invariance is a feature of objects or laws that do not change if scales of length, energy, or other variables, are multiplied by a common factor, and thus represent a universality. The technical term ...

random walk In mathematics, a random walk is a random process that describes a path that consists of a succession of random steps on some mathematical space. An elementary example of a random walk is the random walk on the integer number line \mathbb Z ...

s. This result, now known as ''Strassen's invariance principle'' or as ''Strassen's law of the iterated logarithm'', has been highly cited and led to a 1966 presentation at the

International Congress of Mathematicians The International Congress of Mathematicians (ICM) is the largest conference for the topic of mathematics. It meets once every four years, hosted by the International Mathematical Union (IMU). The Fields Medals, the Nevanlinna Prize (to be rename ...

. In 1969, Strassen shifted his research efforts towards the

with a paper on

Gaussian elimination In mathematics, Gaussian elimination, also known as row reduction, is an algorithm for solving systems of linear equations. It consists of a sequence of operations performed on the corresponding matrix of coefficients. This method can also be used ...

, introducing

Strassen's algorithm In linear algebra, the Strassen algorithm, named after Volker Strassen, is an algorithm for matrix multiplication. It is faster than the standard matrix multiplication algorithm for large matrices, with a better asymptotic complexity, although th ...

, the first algorithm for performing

matrix multiplication In mathematics, particularly in linear algebra, matrix multiplication is a binary operation that produces a matrix from two matrices. For matrix multiplication, the number of columns in the first matrix must be equal to the number of rows in the s ...

faster than the O(''n''³) time bound that would result from a naive algorithm. In the same paper he also presented an asymptotically fast algorithm to perform

matrix inversion In linear algebra, an -by- square matrix is called invertible (also nonsingular or nondegenerate), if there exists an -by- square matrix such that :\mathbf = \mathbf = \mathbf_n \ where denotes the -by- identity matrix and the multiplicati ...

, based on the fast matrix multiplication algorithm. This result was an important theoretical breakthrough, leading to much additional research on fast matrix multiplication, and despite later theoretical improvements it remains a practical method for multiplication of dense matrices of moderate to large sizes. In 1971 Strassen published another paper together with

Arnold Schönhage Arnold Schönhage (born 1 December 1934 in Lockhausen, now Bad Salzuflen) is a German mathematician and computer scientist. Schönhage was professor at the Rheinische Friedrich-Wilhelms-Universität, Bonn, and also in Tübingen and Konstanz. ...

on asymptotically fast integer multiplication based on the

fast Fourier transform A fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT). Fourier analysis converts a signal from its original domain (often time or space) to a representation in th ...

; see the

Schönhage–Strassen algorithm The Schönhage–Strassen algorithm is an asymptotically fast multiplication algorithm for large integers. It was developed by Arnold Schönhage and Volker Strassen in 1971.A. Schönhage and V. Strassen,Schnelle Multiplikation großer Zahlen, ''C ...

. Strassen is also known for his 1977 work with

Robert M. Solovay Robert Martin Solovay (born December 15, 1938) is an American mathematician specializing in set theory. Biography Solovay earned his Ph.D. from the University of Chicago in 1964 under the direction of Saunders Mac Lane, with a dissertation on '' ...

on the

Solovay–Strassen primality test The Solovay–Strassen primality test, developed by Robert M. Solovay and Volker Strassen in 1977, is a probabilistic test to determine if a number is composite or probably prime. The idea behind the test was discovered by M. M. Artjuhov in 1967 ...

, the first method to show that testing whether a number is

prime A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...

can be performed in

randomized polynomial time In computational complexity theory, randomized polynomial time (RP) is the complexity class of problems for which a probabilistic Turing machine exists with these properties: * It always runs in polynomial time in the input size * If the correct ...

and one of the first results to show the power of randomized algorithms more generally.

Awards and honors

In 1999 Strassen was awarded the

, and in 2003 he was co-recipient of the

with

Robert Solovay Robert Martin Solovay (born December 15, 1938) is an American mathematician specializing in set theory. Biography Solovay earned his Ph.D. from the University of Chicago in 1964 under the direction of Saunders Mac Lane, with a dissertation on '' ...

Gary Miller Gary Miller may refer to: *Gary Miller (politician) (born 1948), American politician * Michael Dunn (actor) (Gary Neil Miller, 1934–1973), American actor * Gary L. Miller (1947–1969), American soldier and Medal of Honor recipient * Gary Miller ...

, and

Michael Rabin Michael Rabin ( ; May 2, 1936January 19, 1972) was an American violinist. He has been described as "one of the most talented and tragic violin virtuosi of his generation". His complete Niccolò Paganini, Paganini "24 Caprices" for solo violin are ...

for their work on randomized primality testing. In 2008 he was awarded the

for "seminal and influential contributions to the design and analysis of efficient algorithms."The 2008 Knuth Prize is awarded to Volker Strassen for his seminal and influential contributions to efficient algorithms
ACM SIGACT. In 2011 he won the

of the

Gesellschaft für Informatik The German Informatics Society (GI) (german: Gesellschaft für Informatik) is a German professional society for computer science, with around 20,000 personal and 250 corporate members. It is the biggest organized representation of its kind in the ...

..Konrad-Zuse-Medaille
,

(in German), retrieved 2012-03-09. In 2012 he became a fellow of the

American Mathematical Society The American Mathematical Society (AMS) is an association of professional mathematicians dedicated to the interests of mathematical research and scholarship, and serves the national and international community through its publications, meetings, ...

.List of Fellows of the American Mathematical Society
retrieved 2013-08-05.

References

External links

Home page of Dr. Volker Strassen
* Formulas for fast(er) matrix multiplication and inversion. * {{DEFAULTSORT:Strassen, Volker 1936 births Living people 20th-century German mathematicians 21st-century German mathematicians Theoretical computer scientists Linear algebraists University of Göttingen alumni University of California, Berkeley faculty University of Zurich faculty University of Konstanz faculty Knuth Prize laureates Fellows of the American Mathematical Society