The Path to Discovery
Spielman and Teng first met in the fall of 1990, when Spielman, then an undergraduate at Yale University, visited Carnegie Mellon University to give a speech. Teng, a doctoral candidate there, says he and others at the university admired “this long-haired college junior. He already had two papers of PhD quality. Naturally, he was one of the most prized prospective students that all top universities wanted to attract to their PhD programs.” In 1992, Spielman chose MIT. Teng arrived that same year as an instructor at the Institute. Their student-teacher relationship soon became friendship and then a collaboration that has lasted 11 years.In 1996, after several years of working together in another area, the duo began seeking to improve the simplex method. “The process of research is a lot like trying to find treasure on a dark island with a small flashlight,” says Teng. “We tried to explore those many hopeful leads. Dan always keeps detailed working journals, which systematically mark the maps of the exploration.”
After three years of such work, Spielman had his courtroom realization. The two mathematicians changed their goal and attacked the new research problem in earnest.
Teng, who by then was an associate professor at the University of Illinois at Urbana-Champaign, moved back to Massachusetts on sabbatical and rented an apartment five minutes away from Spielman’s. After that, both researchers turned their living rooms into workspaces. Teng mounted a large whiteboard on his living-room wall. Spielman kept one stored behind his sofa.
From then on, their work together took place at all hours. “It was one of those things where my wife complained that I saw Shanghua more than I saw her for a few years,” Spielman says. Teng worked full time at Akamai in Cambridge, but he went to Spielman’s apartment almost every night after work and on weekends. “We’d stay up for many hours, probably till two, working,” Spielman notes. Teng adds, “I was like an adopted member of Dan’s family. Even their cat, Chloe, became so used to our presence that she would perch in front of the whiteboard and watch attentively whenever we set it up.” The researchers thanked Chloe in their journal paper’s acknowledgments.
To keep track of their work, Spielman continued his working journals, writing down every thought and equation the whiteboards contained before erasing them. Today, a dozen of these 200-page, notebook-size journals line a bookshelf in his Building 2 office. He says about 60 percent of the information the journals contain is work on smoothed analysis. Meanwhile, Teng used a digital camera to take about 40 photographs of the whiteboards before they were erased.