See Inside March 2007

Graph Theory and Teatime

Deep in the heart of Microsoft, Jennifer Chayes and Christian Borgs lead a who's who of mathematics and computer science. The goal? To explore anything they please

Every weekday afternoon some 20 mathematicians and theoretical computer scientists gather in the Seattle suburbs to share tea. The conversation runs from the latest on number theory to the fairest way to decide a closely contested election. The gathering spot is not the faculty lounge of an elite university but rather a meeting area in Building 113, the nondescript glass and steel structure that houses the Theory Group of Microsoft Research.

A decade ago two mathematical physicists--Jennifer Chayes and Christian Borgs--gave up permanent academic positions for the allure of being able to go out and hire the best minds in discrete mathematics, statistical physics and theoretical computer science. By most measures, the pair have succeeded in re-creating the rarefied world of a top university department, right down to the tea ritual. In essence, the group resembles a smaller version of the Mathematical Sciences Research Center in its heyday at the old Bell Labs, home to Claude E. Shannon, Richard Hamming, Narendra Karmarkar and other quantitative luminaries, before corporate upheavals ultimately forced a scaling back. "It would be very hard, if not just impossible, for a university to assemble such a group within a 10-year time frame," remarks Bart Selman, professor of computer science at Cornell University and also a former Bell Labs researcher. "Clearly, Microsoft resources play a role here."

Microsoft Research was established in 1991 to emphasize basic research in computer science at a time when other industrial labs were revamping to focus on more applied endeavors. The Theory Group, whose members routinely publish papers with titles such as "The D4 Root System Is Not Universally Optimal," probably has the least relevance to product development of any Microsoft department.

The disconnect is intentional. In 1996 Nathan Myhrv?old, a former classmate of Chayes at Princeton University who was then Microsoft's chief technology officer, suggested that Chayes and Borgs come to work at Microsoft. "Are you crazy?" Chayes asked Myhr?vold. "You can't make money from what we do."

Myhrvold promised that they would not be enlisted to write code for a new version of Microsoft Office. "He wanted us to do the most way-out stuff," Chayes remembers. "He said, 'Look, I'm not hiring two engineers,'" Borgs chimes in a moment later. The Microsoft offer solved a fundamental problem related to time and space. The two had married four years earlier. Chayes was a tenured professor of mathematics at the University of California, Los Angeles. Borgs had a chaired professorship in statistical physics at the University of Leipzig in Germany.

"We went from living on the other side of the world to doing everything together," Chayes says. Every paper they write bears joint authorship; every intern candidate interviewed receives questions from both. The compatible trajectories stretch back to their youth. Neither followed the rectilinear path set out for them by their parents. Borgs, 49, came from a traditional family in Düsseldorf, Germany, and was expected to take over their 120-year-old chemical business. Chayes, 50, a rebellious "child of the sixties" and the daughter of a Jewish father and a Muslim mother who had immigrated to the U.S. from Iran, was supposed to become a physician. (Her brother, James Tour, also paid no heed to his parents' plans, going on to become a chemist at Rice University and a major figure in nanotechnology.)

The collaborating spouses held Myhrvold to his word and went on to hire some of the best and brightest. There are nine full-time researchers, eight postdoctoral students, five academics on sabbatical from other institutions--and 150 to 200 visitors annually who arrive for stays that range from a day to a month. "Their list of visitors reads like a veritable who's who of theoretical computer science," observes Lenore Blum, a computer scientist at Carnegie Mellon University.

Rights & Permissions
Share this Article:


You must sign in or register as a member to submit a comment.
Scientific American MIND iPad

Give a Gift & Get a Gift - Free!

Give a 1 year subscription as low as $14.99

Subscribe Now >>


Email this Article