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.
This article was originally published with the title Graph Theory and Teatime.