Computer Scientist Who Parlays Failures Into Breakthroughs

Fun examples of thinking about thinking computer science. 

Mordechai Rorvig, Staff Writer

The Computer Scientist Who Parlays Failures Into Breakthroughs  in QuantaMag

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

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.

Spielman has been awarded two Gödel Prizes and the Rolf Nevanlinna Prize, among the top honors in his field.

Brandon Schulman for Quanta Magazine

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.)  ... '