Daniel Spielman

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.

Daniel Spielman received a B.A. (1992) from Yale University and a Ph.D. (1995) from the Massachusetts Institute of Technology. He was affiliated with the Massachusetts Institute of Technology (1996–2005) prior to his appointment to the faculty of Yale University, where he is currently Henry Ford II Professor of Computer Science, Mathematics, and Applied Mathematics in the Department of Computer Science.