“It’s very powerful – the idea of finding better, faster ways to solve problems” observed Daniel Spielman ’92, Professor of Computer Science and Applied Mathematics. He was referencing his work with algorithms, for which he was recently presented the Delbert Ray Fulkerson Prize. Awarded every three years, the prize recognizes outstanding papers in discrete mathematics.
Spielman earned the prize for his groundbreaking developments in a technique called smoothed analysis. In the late 1990s, Spielman and Shang-Hua Teng, Professor of Computer Science at Boston University and a co-recipient of the prize, recognized the power in developing a new method of analyzing programs that is distinct from the more traditional methods, such as “worst case analysis” and “average case analysis”.
These methods are designed to test the speed of programs and their failure modes. “Worst case analysis” easily exposes problem¬atic inputs, but handles them poorly, and “average case analysis” inputs are purely random.
The method of smooth analysis uses inputs near the “worst case,” and perturbs them, which, in essence, smoothes the region of inputs in accordance with its surroundings. This new method of analyzing computer programs has proven to be very effective, emulating reality more closely than either of the previous two methods.
The initial purpose of smoothed analysis was to analyze the simplex algorithm, which it accomplished with much success. Now, smoothed analysis is used in machine learning, optimization, clas¬sical mathematics, linear algebra, and numerous other disciplines. The technique is of critical importance in the field and frequently referenced in papers.
In addition to studying smoothed analysis, Spielman also researches and teaches spectral graph theory.
