Microsoft Research Blog

The Microsoft Research blog shares stories of collaborations with computer scientists at academic and scientific institutions to advance technical innovations in computing, as well as related events, scholarships, and fellowships.

Borgs’ Stellar Work Reaps Its Due Reward

November 25, 2013 | Posted by Microsoft Research Blog

Posted by Rob Knies

Christian Borgs 

Phase transitions. Statistical physics. Probability theory.

To many of us, such concepts are simply beyond our grasp, accessible, if at all, only as something relating, in some vague, hazy fashion, to issues mathematical or topics scientific. Such fields, if they are in the least approachable, beckon only to the special few, those who have scaled the peaks of academia, the brightest of the bright.

Such fields beckoned—and beckon still—to Christian Borgs.

That has become apparent in November 2013, a month in which Borgs, deputy managing director of Microsoft Research New England, has been named a Fellow of not just one, but two prestigious U.S. organizations.

On Nov. 1, he was announced as one of the 2014 Fellows of the American Mathematical Society (AMS), as a member who has made” outstanding contributions to the creation, exposition, advancement,communication, and utilization of mathematics.”

On Nov. 25, Borgs was named a Fellow of the American Association for the Advancement of Science  (AAAS), which elects members whose “efforts on behalf of the advancement of science or its applications are scientifically or socially distinguished.”

As is customary with such honors, they are delivered with a specific citation of the work that earned the Fellowship.

Borgs’ AMS citation reads: “For contributions bringing together analysis, probability theory, graph theory, and combinatorics with mathematical statistical physics and rigorous computer science.”

‘Groundbreaking Research’

The AAAS cites his “groundbreaking research in the mathematical theory of phase transitions, applying methods from statistical physics and probability theory to problems of interest in computer science.”

Phase transitions. Statistical physics. Probability theory. From two seemingly unrelated scientific organizations, a singular pattern emerges.

“This,” he put it in an email communicating the achievements, “seems to be my year.”

Yes, this year—and the last couple of decades that preceded it.

The 2014 class of Fellows is the second in AMS history, which named its inaugural selections a year ago. Of the 50 mathematicians to receive the award in 2014—to be welcomed in Baltimore in mid-January during the organization’s Joint Mathematics Meetings—Borgs was the only industrial researcher. That, he notes, can pay off in a number of ways.

“Obviously,” he says, “Microsoft Research has a great reputation in many fields, but in the field of mathematics, we find that applications to real-world problems, of economic value to Microsoft, can often lead to beautiful, new mathematical theories.”

In 2013, when the first class of AMS Fellows was named, four members of Microsoft Research earned recognition: Jennifer Chayes, Michael Freedman, Yuval Peres, and Madhu Sudan.

“While there are a few other industrial organizations that have one, or maybe two, Fellows,” Borgs observes, “Microsoft Research really stands out, with five now. And another person who would certainly have made it into this group had he not tragically died in a mountain accident a few years ago is Oded Schramm.”

And, Borgs adds, from this deep pool of mathematical talent, entirely new fields have emerged during the individuals’ time at Microsoft.

“Michael Freedman started a topological theory of quantum computing,” Borgs says, “that may still be our best shot at actually building a quantum computer capable of breaking all known crypto systems. And a group consisting of Jennifer, Laci Lovász (another inaugural-class AMS Fellow who was at Microsoft Research) and I started the theory of graph limits, which is now a thriving subfield of graph theory and combinatorics, helping us understand really large graphs such as the World Wide Web.”

Almost exactly a month after Borgs accepts his AMS honor, he’ll be in Chicago to be inducted as an AAAS Fellow on Feb. 15 during the AAAS Annual Meeting. Pivoting from mathematics to science, he mentions collaborative work he has undertaken with Chayes, Riccardo Zecchina of the International Centre for Theoretical Physics, and many collaborators, including Microsoft Research New England postdoc Antony Gitter and Ernest Fraenkel of the Massachusetts Institute of Technology.

“The part of my work that most exemplifies this aspect of science,” Borgs says, “concerns applications of belief propagation to systems biology. These methods, originally developed in coding theory to decode many codes of practical importance, were adopted by our research group to deal with problems that mathematicians would call Steiner Tree problems.”

The application of his research experience to biological concerns continue to capture Borgs’ attention, even as he prepares to open the new year with a busy schedule of travel and accolades.

Plenty of Challenges

“I am working on many problems,” Borgs says, “from problems in biology concerning patient-specific pathways in cancer—a research area that hopes eventually to lead to what the press calls ‘personalized medicine’—via problems involving network algorithms for huge graphs where even algorithms linear in the input are too slow for the problems we are facing.”

The latter, he explains, are important for search on the World Wide Web, as well as for marketing on social networks. Such concerns provide motivation for that special few who excel at this sort of exotic yet fascinating endeavor.

“I also am investigating deep mathematical problems,” Borgs says, “building on our theory of graph limits and motivated by trying to come up with models for large, real-world networks, whether they describe the Internet or social networks.”

For some, it seems, the world is simply a crucible of issues to be addressed, questions to be answered, with acclaim to follow in its own due time. For Christian Borgs, that time is now.