Daniel Spielman Wins MacArthur ‘Genius’ Award

The MacArthur Foundation has announced its Class of 2012, which includes 23 Fellows, with Daniel Spielman, Henry Ford II Professor of Computer Science, Mathematics, and Applied Science at Yale University, being the sole computer scientist.

From the MacArthur announcement:
"Daniel Spielman is a theoretical computer scientist studying abstract questions that nonetheless affect the essential aspects of daily life in modern society—how we communicate and how we measure, predict, and regulate our environment and our behavior. Spielman’s early research pursued aspects of coding theory, the mathematical basis for ensuring the reliability of electronic communications. When transferring digital information, sometimes even one incorrect bit can destroy the integrity of the data stream; adding verification 'codes' to the data helps to test its accuracy. Spielman and collaborators developed several families of codes that optimize speed and reliability, some approaching the theoretical limit of performance. One, an enhanced version of low-density parity checking, is now used to broadcast and decode high-definition television transmissions. In a separate line of research, Spielman resolved an enduring mystery of computer science: why a venerable algorithm for optimization (e.g., to compute the fastest route to the airport, picking up three friends along the way) usually works better in practice than theory would predict. He and a collaborator proved that small amounts of randomness convert worst-case conditions into problems that can be solved much faster. This finding holds enormous practical implications for a myriad of calculations in science, engineering, social science, business, and statistics that depend on the simplex algorithm or its derivatives. Most recently, Spielman has championed the application of linear algebra to solve optimization problems in graph theory. He and his colleagues have offered a new approach to maximizing the flow through unidirectional graphs, promising significant improvements in the speed of a wide range of applications, such as scheduling, operating system design, and DNA sequence analysis. Through these projects and fundamental insights into a host of other areas, such as complexity theory and spectral theory, Spielman is connecting theoretical and applied computer science in both intellectually and socially profound ways."

Spielman was previously awarded the Gödel Prize for his joint work on smoothed analysis  of algorithms in 2008. He received the Nevanlinna Prize "for smoothed analysis of Linear Programming, algorithms for graph-based codes and applications of graph theory to Numerical Computing" in 2010, and was named a Fellow of ACM the same year.

 

Jack Rosenberger is senior editor, news, of Communications.