Daniel Spielman solves important problems by thinking hard — about other questions

June 13, 2022

Article from Quanta Magazine by Mordechai Rorvig, Staff Writer.

The Computer Scientist Who Parlays Failures Into Breakthroughs

Nestled among the impressive domes and spires of Yale University is the simple office of Daniel Spielman. His shelves are lined with tall black notebooks, containing decades of handwritten notes, and against a wall sits a large, comfortable couch that looks particularly well used.

“I’m sort of built for sitting still and thinking,” he admitted.

What he thinks about, amid the gothic grandeur of the campus, is a slightly more modern topic: computer science. And over his career, Spielman has produced a slew of influential results, although as he describes it, failure has been his most common outcome. “The key point is you have to enjoy the process of working,” he said. “As long as I enjoy that process, then it’s OK — as long as there’s success once in a while.”

Spielman first came to Yale as an undergraduate before attending graduate school at the Massachusetts Institute of Technology, where he earned his doctorate in 1995. While there, he studied the methods used to protect communications from interference, which involved so-called error-correcting codes. Robert Gallager had shown in 1963 how these codes could be built from graphs — mathematical objects consisting of dots (vertices) connected by lines (edges) — but by Spielman’s time, this approach was largely forgotten. Spielman and his adviser, Michael Sipser, were among the few who revived it to create new codes built from special graphs called expander graphs. The codes they invented became the basis for much subsequent work in coding theory, including a major recent breakthrough.

While at MIT, Spielman met the researcher Shang-Hua Teng, now at the University of Southern California, whose career would become intertwined with his own. One of their most fruitful collaborations involved explaining a widely used algorithm called the simplex method, for which they were awarded the Gödel Prize, an annual prize for outstanding work in theoretical computer science.

The pair went on to win a second Gödel Prize for coming up with algorithms that can quickly solve large sets of simple linear equations. The sets of equations they studied come up whenever scientists model simple physical systems, like heat flow or electrical currents, making their algorithm one of great practical importance.

For these results, in 2010 Spielman was awarded the Rolf Nevanlinna Prize, given every four years to an outstanding information scientist less than 40 years old. (The prize has since been renamed the IMU Abacus Medal.)

Most recently, Spielman has turned his attention to the mathematics behind randomized controlled trials, which underpin modern medical studies. The organizers of these trials try to randomly split study subjects between a test group, which receives an experimental treatment, and a control group, which doesn’t. However, finite-size groups always end up with an imbalance in some category, such as age or weight or blood pressure. Along with his research group, Spielman has worked to find algorithms for achieving a better balance. Despite a slow start, the project has gone better than Spielman expected. “We haven’t declared it a failure yet,” he said.

Quanta sat down with Spielman in his office to talk about the power of thinking, what makes a successful collaboration, and how research is like gambling. The interview has been condensed and edited for clarity, and can be read here.