# 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.

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.

** TR**: How have you been led to some of the problems you’ve worked on recently? What’s been the source of some of your questions?

**JC**: For me personally, having been at a company this past decade rather than having remained in academia meant that I got to hear about some problems much more quickly than I would have otherwise. I got to take some of these exciting things that were happening in the real world and be one of the first people to model it, because I was hearing about it. Then I could take those problems out into the mathematics community and get other people working on them. For example, I heard about link spam really early in the game, and how it affects the quality of search-engine results. Also, I hear everyone talking about social networks at a different level than if I were at the university. I’m convinced that people who study graphical systems and networks at universities are all going to be looking at recommendation systems three or four years from now. But I got to look at them a bit earlier, because people around me were asking, “How would we monetize a social network?”

** TR**: You’ve studied that problem with your work on recommendation systems. But recently, Facebook, for example, has struggled with some of its efforts to monetize. Its Beacon advertising system suffered from this tension between sharing information through a network and protecting the privacy of members of the network. What can be done about this?

**JC**: Those are exactly the kinds of questions that we’re asking. We’ve looked at how to design systems that have various properties. We might come up with a theorem saying you can’t have a recommendation system that will deliver all the information you want and have all the privacy. But then you could say, “Okay, which properties am I willing to give up, and which kinds of recommendation systems will have the kinds of properties that I want?” We want to work with sociologists, psychologists, and economists in our new lab partly because I’m a mathematician and can model these kinds of things. I can get a mathematical formulation of various forms of privacy, but I might not be able to tell you what the majority of people want, or what people in a certain age group want. So if I work with sociologists and psychologists, they can suggest to me various different kinds of properties and order those properties for me. Then I can come up with a mathematical framework and say, “Here is an algorithm that will give you a recommendation that has the maximum number of properties in that ranked order.” With all the data that we’ve got and the kinds of things that we want to do, I think it’s really time for mathematicians and computer scientists to start interacting with sociologists and psychologists. I’m not an expert in what people want. I can just model what people want.

** TR**: Will this sort of thinking guide your approach in the new lab?

**JC**: I’m hoping that our new lab in Cambridge will be the perfect environment in which to look at these kinds of questions. We’re going to try to bring together all the right people.