Thursday, February 21, 2008

Applying Theory at Microsoft

Jennifer Chayes, managing director of the forthcoming Microsoft Research New England lab, talks about the importance of math to the Internet.

By Erica Naone

Microsoft mathematician: Jennifer Chayes, above, is managing director of the Microsoft Research New England lab, which will open in July. Chayes, who began her career in academia, has found that her abstract mathematical research has applications to search, keyword advertising, recommendation systems, and social networks. Credit: Microsoft

Before she was recruited by Microsoft Research, Jennifer Chayes was a professor of mathematics at UCLA. Although mystified at the time as to what the software giant might want with her heavily theoretical work, Chayes has gone on to do research that has wide-reaching applications on the Internet, including search, keyword advertising, recommendation systems, and social networks. Having previously cofounded the Microsoft Research Theory Group, Chayes is now managing director of the Microsoft Research New England lab, which will open in Cambridge, MA, in July. Technology Review recently asked Chayes about the transformation her work has undergone, and how she might carry her research forward in the new lab.

Technology Review: When you were hired 11 years ago by then-CTO Nathan Myhrvold, you thought your work was irrelevant to Microsoft's business. What's changed since then?

Jennifer Chayes: It's funny. I was recently talking to someone in my group who said, "Our work has moved so much closer to applications over the past decade." I said to him, "No, what's happening is that applications are moving so much closer to us." When Nathan decided to hire me and my husband, Christian [Borgs], we were dealing with discrete mathematics problems with a lot of variables and a lot of complicated interactions, and he saw the potential for that becoming relevant. I don't think Nathan foresaw all the applications of a World Wide Web, social networks, and all of that, but he foresaw that having people who study these kinds of things could be useful.

TR: Your PhD was in mathematical physics, and even that research has been useful to Microsoft. How did phase transitions, such as the transformation from solid to liquid, turn out to be important to computer science?

JC: Around 1995, there were a couple of people who started looking at phase transitions in these hard computer-science problems where you have to balance a given amount of resources against a set of constraints. It turns out if you have a parameter that measures the ratio of resources to constraints, the system undergoes a transition which is mathematically just like the phase transition where a liquid freezes or boils. It's mathematically the same kind of thing where you pass through this point at which you're just able to satisfy the constraints, and then you're not able to satisfy them anymore. It turns out that studying the phase transition in these constraint-satisfaction or resource-allocation problems has led to some of the very fastest algorithms known for figuring out the optimal structure of networks. Who would have thought? Recently, I was at a Bill Gates review where Bill heard about what research is being done. We've been looking at multicasting, and trying to find the most efficient way to broadcast something over the Web to a certain number of people. Someone mentioned some work that my group has done recently to come up with a very fast multicast algorithm, based on this phase-transition work. Ten years ago, I had been telling Bill about it and said it was great that he was hiring people whose work wouldn't pay off for 100 years. And here it is 10 years later, and the work is really paying off in these superfast algorithms.