The Computer Scientist Who Parlays Failures Into Breakthroughs

The simple office of Daniel Spielman is located near the domes and spires of Yale University. His shelves are lined with tall black notebooks, with decades of handwritten notes, and against a wall sits a large, comfortable couch.

He admits that he is built for sitting still and thinking.

He thinks about computer science when he's on the campus. Although he describes it as his most common outcome, failure has been the most influential result over his career. He said you have to enjoy the process of working. "As long as I enjoy that process, then it's ok, as long as there's success once in a while."

After graduating from Yale as an undergrad, he went to graduate school at the Massachusetts Institute of Technology to get his PhD. He was studying the methods used to protect communications from interference. Robert Gallager showed how graphs could be used to build these codes in 1963, but by the time of Spielman, this approach was mostly forgotten. Special graphs called expander graphs were used to create new codes. A major recent breakthrough in coding theory is the result of the code they invented.

He met the researcher at the University of Southern California, who would become intertwined with his own career. The Gdel Prize, an annual prize for outstanding work in theoretical computer science, was one of their most fruitful collaborations.

They won a second Gdel Prize for coming up with a way to solve large sets of simple linear equations. When scientists model simple physical systems, like heat flow or electrical currents, the sets of equations they studied are very important.

The Rolf Nevanlinna Prize is given to an outstanding information scientist younger than 40 years old. The prize has been changed.

Modern medical studies are underpinned by the mathematics of randomized controlled trials. The trials try to split the study subjects into two groups, one that gets an experimental treatment and another that doesn't. Age, weight, and blood pressure are just a few of the categories that a finite-size group always ends up with. Along with his research group, Spielman has been looking for ways to achieve a better balance. The project went better than anticipated despite a slow start. He didn't say that it was a failure yet.

The power of thinking, what makes a successful collaboration, and how research is like gambling were some of the topics discussed by the two men. The interview has been edited to make it clearer.

This editorially independent publication has received research funding from the Simons Foundation since 2012

How did you get started in computer science?

There was a book in the library about computers. It sounded like the most amazing thing I've ever heard. They were talking about how to program a robot, and how to organize it. I really wanted a computer after that. At some point, my parents came across an old Commodore computer that was being sold. We got all the engineer's magazines and books, which was great. I looked through them. I just learned to program after spending a lot of time reading.

Poring through books alone as a kid sounds tough. How did you get through it?

I like to push through things. I enjoyed thinking when I was young. Until I got a computer, I didn't have anything to think about. I suppose you could say I'm obsessed with things. I like to get things done very quickly. It doesn't stop me from getting frustrated.

It's probably the same thing that keeps a gambler going. I think I solved a problem with my brilliant idea. I will be very happy about it. I won't be able to fall asleep. My wife will tell me to go to sleep and find the bug in the morning. She knows that I haven't solved anything. It is a big rush when you think you have solved a problem. Even if you're wrong, the feeling of excitement is still motivating.

One of the major developments of computer science at the time was the understanding of checkable proof. The idea of relating them to expander graphs was not useful, but I realized it was useful for error-correcting codes. We failed to solve the problem but what we developed was useful. The expander codes felt like an accident to us.

It is true with my research. It is not the problem I was trying to solve that makes the way I do things. I was trying to solve something else and it didn't work. I knew that I could use it for something.

Is that what happened with Shang-Hua Teng and smoothed analysis?

It felt like it was a long time ago. Shang-Hua lived in our apartment. It came out of a project that I and Shang-Hua had worked on before.

How did you get started on smoothed analysis?

We don't have a good explanation for why a lot of things people do in practice work for them. The simplex method was used a lot and we were trying to understand how it works. It was used very successfully despite the fact that it would fail. We weren't sure how to explain this. We came up with the idea that it works because the cases where it doesn't work seem very fragile.

We had been coding them up. Things that were supposed to break the simplex method didn't, if we weren't careful with the numerical precision. If there was some randomness in the inputs, the method would work. We proved that. It was an influential idea because it helped people understand why this one algorithm worked, and because people have used the idea and concept to understand why a lot of other programs work.

Why do you think your collaborations with Teng were so successful?

He was an instructor at MIT when I was a graduate student. We had a very compatible working style. There is a couch in my office. There were two couches in my office. When you have an idea, get up and talk about it, and that means that I and Shang-Hua were both able to work. He was happy to think about things and talk about them. He was happy to work on problems that we wouldn't solve. Even if we were working on something for a long time, failure was the result. That was okay.

At first glance, the topic of controlled trials seems more straightforward than these other problems. What’s so hard about splitting people into groups?

This is how you think of it. If I give you a coin and you flip it 10 times, you will see patterns in it, even if they were randomly generated. If you only give me a few quantities to measure, like age and gender, and you only give me 100 people, then there will be a discrepancy in one of those. Being completely random is not a good idea.

So you want to walk some kind of tightrope of randomness?

It's called "fully random." It's a tradeoff between being completely random and balancing the quantities that you care about. It's better to balance things out if they have a small impact on the outcome. I initially thought we would have to balance things out, but it turns out we only need a small amount of randomness. This is new. Most of the results said there were good divisions, but they didn't tell you how to find them It was a breakthrough result from the year 2009, and it was the first time we were able to do this efficiently. We use computer science results to make balanced divisions. People didn't think about using these before

Ultimately, why work on such hard problems in the first place, where failure seems to happen so often?

It's a big risk. I would be excited to give talks if I solved those things. I don't work on things on a daily basis. Some of those are around. I don't have as much motivation to spend time on other problems. All research is difficult for me. Problems that look easy are hard to work on. If I am going to be doing something that is hard, why not work on something that is high impact or that other people think are hard as well?

Astronomers Reimagine the Making of the Planets