Rolf Nevanlinna Prize – Daniel Spielman
Daniel Spielman of Yale University, USA, 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.
Rolf Nevanlinna Prize - Daniel Spielman, Yale University
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 Shanghua 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.
Brief Biodata
Daniel Alan 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 M. I. T. in 1995. His thesis was on ‘Computationally Efficient Error-correcting Codes and Holographic Proofs’. He spent a year as a National Science Foundation (NSF) 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 won several awards and honours earlier, chief among them being the Fulkerson Prize, jointly awarded by the American Mathematical Society (AMS) and the Mathematical Programming Society (MPS) in 2009; the Gödel Prize, jointly awarded by the Association for Computing Machinery (ACM) and the European Association for Theoretical Computer Science (EATCS) for Spielman and Teng’s paper on ‘Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time’.
Spielman has applied for five patents for error-correcting codes that he has invented and four of them have already been granted by the U. S. Patent Office.
Contact
Email: spielman at cs.yale.edu
Phone: (203)436-1264
Mailing address: Department of Computer Science, Yale University, New Haven, CT 06520-8285, USA.
