Daniel Spielman, Ph.D.

Daniel Spielman’s work has been important to three distinct research communities: theoretical computer science, applied mathematics, and operations research. His work on smoothed analysis of linear programming provides mathematical justification for why the simplex method to solve problems works well in practice even though worst-case analysis shows that there are instances in which it takes exponential time. A small random perturbation converts any linear programming instance into one that, with high probability is solved efficiently by the simplex algorithm. Similar perturbation results hold for many other problems and provide an alternative to worst-case analysis, which may be too pessimistic. His codes based on expander graphs achieve near-optimal rate and nearly linear time encoding and decoding algorithms. In joint work with Teng, Spielman gave a method of preconditioning a Laplacian matrix A, which yields a near-linear-time algorithm for solving the system Ax = b. This leads to highly efficient algorithms for circuit analysis and network flow computations.