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.[break]
The couple's overlapping orbitals have been good for their careers and for Microsoft.
The quasi-academic environment has enabled notable researchers to continue their work undistracted--or, if they so choose, to branch out in new directions. Oded Schramm devised a mathematical proof that shows how certain random two-dimensional objects, when distorted, retain the same statistical properties--a characteristic called conformal invariance. One of Schramm's colleagues, Wendelin Werner, received the Fields Medal for this work. (Schramm was a few weeks too old to qualify for the medal, bestowed only on those younger than 40.) "Oded basically invented a new branch of mathematics, which I predict will be studied 100 years from now," Chayes says.
Another notable was Michael Freedman, who won the Fields Medal while at the University of California, San Diego, for his work on the Poincaré conjecture. He moved to the Theory Group in 1997 and began to explore in earnest how topological quantum field theory could be applied to create a quantum computer with very low error rates, taking advantage of the fact that topological properties resist perturbations (errors). Freedman has since formed his own group within Microsoft that focuses on quantum computation.
A younger researcher at 32, Henry Cohn has, along with postdoc Abhinav Kumar, published seminal work on how densely spheres can be packed together within eight and 24 dimensions. Mathematicians are fascinated by what Cohn calls these "miracle dimensions" because of packing efficiencies generally not found elsewhere. Such calculations may ultimately enable better error-correction codes for transmitting digital bits on noisy channels.
Chayes and Borgs have also been able to build on their original university work on the mathematics of phase transitions: sudden discontinuities in a physical state, such as when water turns to ice. Similarly, whenever increasing loads are placed on two parallel microprocessors, a phase transition occurs in which balancing work among the processing elements becomes much more difficult. In their papers, Chayes and Borgs have shown that once the transition has occurred, it may be virtually impossible to improve on a near-optimal solution to partitioning a workload--the programmer of a parallel processor cannot just shift some of the load from one processor to another to achieve the best balance. "You may as well start over," Chayes says. "That's a disaster for computation."
Besides computer science, this type of optimization problem has implications for modeling the precise networks of chemical bonds, genes and synapses that are found in investigations of protein folding, gene activation in microarray chips, and the changes in neural connections that occur during learning. Chayes and Borgs have undertaken a collaborative initiative with Riccardo Zecchina of the International Center for Theoretical Physics in Trieste, Italy, and other European researchers to explore a technique, called survey propagation, that might find better solutions for the hard optimization problems found after a phase transition occurs.
Chayes and Borgs's prior university labors on graph theory and phase transitions have been of some use to the enterprise. Since they joined Microsoft, the World Wide Web has come into its own. "All of a sudden the stuff we were doing has become relevant," Chayes notes. Graph theory serves as a powerful tool for modeling the complexity of the Web. Chayes and Borgs have shown how the patterns formed by links fanning out from spam sites differ in appearance from connections to normal sites, a tool that is being incorporated into search engines by Microsoft product developers.
For the pair, the fusion of work and personal life has proved essential for building both the Theory Group and continuing their own research. Certainly Borgs understands Chayes when she gets angry at her husband and shouts, "You're perturbing around the wrong ground state." The couple's overlapping orbitals have been good for their own careers, for Microsoft and for the larger community of mathematicians and computer scientists.