The Laureates

Copyright © Klaus Tschira Stiftung / Peter Badge

Daniel Spielman

Born March 1970 in Philadelphia, Pennsylvania (USA)

Rolf Nevanlinna Prize (2010) “for smoothed analysis of Linear Programming, algorithms for graph-based codes and applications of graph theory to Numerical Computing.”

Daniel Spielman studied Mathematics and Computer Science at Yale University and earned his Bachelor’s degree in 1992. He then received his doctorate from Massachusetts Institute of Technology (MIT) with a thesis on ‘Computationally Efficient Error-Correcting Codes and Holographic Proofs’ (Ph.D. 1995). He then conducted one year of research funded by the National Science Foundation at the Computer Science department of the University of California, Berkeley, before returning to the Department of Applied Mathematics at MIT (1997-2005). Since then he has worked as a professor at Yale University, currently as the Henry Ford II Professor of Computer Science, Mathematics, and Applied Mathematics.

Spielman has already received numerous awards. Besides the Nevanlinna Prize, he was for example awarded the Doctoral Dissertation Award of the Association for Computing Machinery (1995), the IEEE Information Theory Paper Award (2002), the Gödel Prize (2008, together with Shang-Hua Teng), and the Fulkerson Prize (2009, also together with Shang-Hua Teng).

Daniel Spielman works in the field of numerical linear algebra, as well as in theoretical computer science and combinatorics. He became known in the community for developing ‘smoothed analysis’, which he introduced together with Shang-Hua Teng in 2001 in a work entitled ‘Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time’. The simplex algorithm is one of the most important algorithms for optimization in the last 50 years. It solves linear programs, which are optimization problems that occur very often in business and industry. However, there are problems that can not be solved quickly with the simplex algorithm, and therefore it is traditionally considered ‘slow’ in a mathematical sense. However, those worst-case optimization tasks are artificially constructed and do not occur in practice. On the contrary, for most practical problems, the algorithm proves to be fast, even in the mathematical sense. Spielman and Teng therefore adapted the analysis of the effectiveness of algorithms to reality. With their sophisticated method, rogue problems are ignored as long as they can be easily changed into readily soluble problems; in this sense, the analysis of effectiveness is ‘smoothed’.

A second area of Spielman’s research is coding theory, the theory that is concerned with how to encode data before transmitting it over networks. The construction of codes which can be quickly decoded is closely connected to graph theory. Together with his doctorate superviser Michael Sipser, Spielman constructed even in his dissertation codes that can effectively correct transmission errors and can at the same time be decoded extremely quickly; they used for this special graphs, or ‘expanders’. Spielman now holds four patents on error-correcting codes.

Using methods from graph theory, Spielman and Teng designed fast algorithms for problems in numerical linear algebra, such as the solution of a certain class of linear systems of equations known as Laplacian Linear Systems.