Daniel Spielman of Yale University, New Haven, CT, has been chosen for the 2010 Rolf Nevanlinna Prize "for smoothed analysis of Linear Programming, algorithms for graph-based codes and applications of graph theory to numerical computing."
The prize is awarded once every four years at the International Congress of Mathematicians, for outstanding contributions in mathematical aspects of information sciences.
Linear Programming is one of the most useful tools in applied mathematics. The oldest algorithm for Linear Programming, the Simplex Method, works very well in practice, but mathematicians have been perplexed about this efficacy and have tried for long to establish this as a mathematical theorem. Spielman and his co-author Shenhua Teng developed a beautiful method and proved that, while there may be pathological examples where the method fails, slight modifications of any pathological example yields a "smooth" problem on which the Simplex Method works very well.
A second major contribution of Spielman is in the area of coding. Much of the present-day communication uses coding, either for preserving secrecy or for ensuring error correction. An important technique to make both coding and decoding efficient is based on extremely well-connected graphs called expanders. Spielman and his co-authors have done foundational work on such codes and have designed very efficient methods for coding and decoding. These codes provide an efficient solution to problems such as packet-loss over the internet and are particularly useful in multicast communications. They also provide one of the best known coding techniques for minimizing power consumption required to achieve reliable communication in the presence of white Gaussian noise.
Spielman was born in Philadelphia in March 1970. He received his B.A. in mathematics and Computer Science from Yale in 1992, and his Ph.D. in Applied Mathematics from MIT in 1995. His thesis was on "Computationally Efficient Error-correcting Codes and Holographic Proofs." He spent a year as a U.S. National Science Foundation post-doctoral fellow in the Computer Science Department at University of California, Berkeley, and then taught at the Applied Mathematics Department of MIT until 2005. Since 2006 he has a Professor of Applied Mathematics and Computer Science at Yale University.
Spielman has applied for five patents for error-correcting codes, four of which have been granted by the U. S. Patent Office.