The Computer Scientist Who Parlays Failures Into Breakthroughs

Daniel Spielman solves important problems by thinking hard — about other questions. “For most of the problems that I’ve solved, I can identify the moment and tell the story about the moment where a certain solution came into my mind,” Spielman said. “But that’s just because I’ve spent an absurd amount of hours working on them.”

Mordechai Rorvig in Quanta: 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.

In performing research, Spielman uses a variety of methods, like pencil and paper calculations, computer experiments and simply sitting and thinking.

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.

“I have a really lousy memory,” said Spielman. “When I need to remember things, I remember better if I read my notes.”

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.

Graphs are essential in much of Spielman’s work.

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.

More here.