Christian Borgs
Christian Borgs is deputy managing director of the new
Microsoft Research New England lab in Cambridge, Massachusetts, which opened in July 2008. He is also an affiliate professor of mathematics at the
University of Washington. Before becoming deputy managing director of the New England lab, he was a principal
researcher and co-manager of the Theory Group at
Microsoft Research.
His research is at the interface of mathematics, physics, and
theoretical computer science. In addition to his original area of expertise,
the mathematical theory of first order phase
transitions, his current interests include the following areas:
- phase transitions in
combinatorics and theoretical computer science
- graph theory, structural
and dynamical properties of networks
- analysis of Monte Carlo
Markov chains
- algorithmic game theory and
recommendation systems
|
Christian Borgs studied physics at the
University of Munich, the
University Pierre et Marie Curie in Paris, the
Institut des Hautes Etudes in
Bures-sur-Yvettes, and the
Max-Planck-Institute for Physics in Munich. He received his Ph.D. in
mathematical physics from the University of Munich, held a postdoctoral fellowship at
the
ETH Zurich, and received his
Habilitation in mathematical physics from the
Free University in Berlin. After
his Habilitation he became the C4 Chair
for Statistical Mechanics at the
University of Leipzig, and in 1997 he
joined Microsoft Research to co-found the Theory Group.
He is well known for his work on the mathematical theory of
first-order phase transitions and finite-size effects, for
which he won the 1993 Karl-Scheel Prize of the German Physical
Society. Since joining Microsoft, Christian Borgs has become one of the
world leaders in the study in phase transitions in
combinatorial optimization, and more generally, the use of
methods from statistical physics and probability theory in
problems of interest to computer science and technology. He is one of the top
researchers in the
modeling and analysis of self-organized networks, such as the
Internet, the World Wide Web and social networks.
Christian Borgs is the co-author of more than 90 research papers and is the
co-inventor of more than 20 patents. Among the honors he has
received are a scholarship from the German National Merit Foundation,
the above mentioned
Karl-Scheel Prize, and the
Heisenberg Fellowship
of the German Research Council. He has
also given the prestigious Conference Board of Mathematical
Sciences (CBMS) lecture series entitled "Statistical Physics
Expansion Methods in Combinatorics and Computer Sciences." He
has been a long-term visitor at Princeton,
Harvard, and
UCLA,
and has twice been a member of the Institute for Advanced Study
in Princeton. Among the boards and councils on which he has
served are the Council of the University of Leipzig, the
Editorial Boards of the Journal of Statistical Physics and the
SIAM Journal on Discrete Mathematics, and the Board of Trustees
of the Institute for Pure and Applied Mathematics (IPAM).
Christian Borgs is married to Jennifer Chayes, who is also at
Microsoft Research, and with whom he collaborates on most of
his scientific work. In his rare spare time, he enjoys art,
theatre and classical music, as well as skiing and swimming.
Selected Publications
Phase Transitions in Combinatorics
and Computer Science
 |
Uniform boundedness of crossing probabilities implies hyperscaling
(with J. T. Chayes, H. Kesten and J. Spencer)
Random Structures and Algorithms 15, 368-413 (1999).
|
|
|
The birth of the infinite cluster: Finite-size scaling in percolation
(with J. T. Chayes, H. Kesten and J. Spencer)
Communications in Mathematical Physics 224, 153-204 (2001).
|
|
|
The scaling window of the 2-SAT transition
(with B. Bollobas, J. T. Chayes, J.H. Kim and D.B. Wilson)
Random Structures and Algorithms 18, 201-256 (2001).
|
|
|
Sharp threshold and scaling window for the integer partitioning problem
(with J. T. Chayes and B. Pittel)
Proceedings of the 33rd annual ACM Symposium on the Theory of Computing (STOC), 330-336 (2001).
|
|
|
Phase transition and finite-size scaling for the integer partitioning problem
(with J. T. Chayes and B. Pittel)
Random Structures and Algorithms 19, 247-288 (2001).
|
|
|
Constrained integer partitions
(with J. T. Chayes, S. Mertens and B. Pittel)
Proceedings of the 6th Latin American Symposium on Theoretical Information
(LATIN), 59-68, Lecture Notes in Computer Science 2976 (2004).
|
|
|
Phase diagram for the constrained integer partitioning problem
(with J. T. Chayes, S. Mertens and B. Pittel)
Random Structures and Algorithms 24, 315-380 (2004).
|
|
|
Random subgraphs of finite graphs: I. The scaling window
under the triangle condition
(with J. T. Chayes, R. van der Hofstad, G. Slade and J. Spencer)
Random Structures and Algorithms 27, 137-184 (2005). |
|
|
Random subgraphs of finite graphs: II. The lace expansion
and the triangle condition
(with J. T. Chayes, R. van der Hofstad, G. Slade and J. Spencer)
Annals of Probability 33, 1886-1944 (2005). |
|
|
Random subgraphs of finite graphs: III. The phase transition
for the n-cube
(with J. T. Chayes, R. van der Hofstad, G. Slade and J. Spencer)
Combinatorica 26, 395-410 (2006). |
|
|
The Kesten-Stigum reconstruction bound is tight for roughly symmetric
binary channels
(with J. T. Chayes, E. Mossel and S. Roch)
47th Annual IEEE Symposium on Foundations of Computer Science (FOCS),
518-530 (2006).
|
|
|
Percolation on dense graph sequenses
(with B. Bollobas, J. T. Chayes and O. Riordan)
Preprint (2007).
|
|
|
Proof of the local REM conjecture for number partitioning I: Constant
energy scales
(with J. T. Chayes, S. Mertens and C. Nair)
Random Struct. Algorithms 34, 217-240 (2009). |
|
|
Proof of the local REM conjecture for number partitioning II: Growing
energy scales
(with J. T. Chayes, S. Mertens and C. Nair)
Random Struct. Algorithms 34, 241-284 (2009). |
Networks and Graph Theory
|
|
Directed scale-free graphs
(with B. Bollobas, J. T. Chayes and O. Riordan)
Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA),
132-139 (2003).
|
|
|
Degree distribution of the FKP network model
(with N. Berger, B. Bollobas, J. T. Chayes and O. Riordan)
Proceedings of the 30th International Colloquium on Automata, Languages and
Programming (ICALP), 725-738, Lecture Notes in Computer Science 2719 (2003).
|
|
|
Exploring the community structure of newsgroups
(with J. T. Chayes, M. Mahdian and A. Saberi)
Proceedings of the 10th ACM SIGKDD International Conference on
Knowledge, Discovery and Data Mining (KKD), 783-787 (2004).
|
 |
Newsgroup cluster data referred to in the above paper.
|
|
|
Competition-induced preferential attachment
(with N. Berger, J. T. Chayes, R. D'Souza and R. D. Kleinberg)
Proceedings of the 31st International Colloquium on Automata, Languages and
Programming (ICALP), 208-221, Lecture Notes in Computer Science 3142 (2004) |
|
|
Degree distribution of competition-induced preferential attachment
graphs
(with N. Berger, J. T. Chayes, R. D'Souza and R. D. Kleinberg)
Combinatorics, Probability and Computing 14, 697-721 (2005). |
|
|
On the spread of viruses on the Internet
(with N. Berger, J. T. Chayes and A. Saberi)
Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithm (SODA), 301-310 (2005). |
|
|
Graph limits and parameter testing
(with J. T. Chayes, L. Lovasz, V. Sos, B. Szegedy and K. Vesztergombi)
Proceedings of the 38rd Annual ACM Symposium on the Theory of Computing (STOC),
261-270 (2006).
|
|
|
Counting graph homomorphisms
(with J. T. Chayes, L. Lovasz, V. Sos, B. Szegedy and K. Vesztergombi)
in Topics in Discrete Mathematics (eds. M. Klazar, J. Kratochvil, M. Loebl, J. Matousek, R. Thomas, P. Valtr),
315-371, Springer (2006). |
|
|
Convergent sequences of dense graphs I: Subgraph frequencies,
metric properties and testing
(with J. T. Chayes, L. Lovasz, V. Sos, and K. Vesztergombi)
Preprint (2006). |
|
|
Convergent sequences of dense graphs II: Multiway Cuts and Statistical Physics
(with J. T. Chayes, L. Lovasz, V. Sos, and K. Vesztergombi)
Preprint (2007). |
|
|
Emergence of tempered preferential attachment from optimization
(with N. Berger, J. T. Chayes, R. D'Souza and R. D. Kleinberg)
Proceedings of the National Academy of Sciences (PNAS) 104, 6112-6117 (2007),
cover article. |
|
|
Fitting the WHOIS Internet data A short note with technical
details left out in the above paper.
|
|
|
First to Market is not Everything: an Analysis of Preferential
Attachment with Fitness
(with J. T. Chayes, C. Daskalakis and S.Roch)
Proceedings of the 39rd annual ACM Symposium on the Theory of Computing (STOC), 135-144 (2007). |
tr valign=middle>
|
How to distribute antidote to control epidemics
(with J. T. Chayes, A. Ganesh, and A. Saberi)
Preeprint (2008). |
Algorithmic Game Theory and Recommendation Systems
|
|
Multi-unit auctions with budget-constrained bidders
(with J. T. Chayes, N. Immorlica, M. Mahdian and A. Saberi)
Proceedings of the 6th ACM Conference on Electronic Commerce (EC), 44-51 (2005). |
|
|
Bid optimization in online advertisement auctions
(with J. T. Chayes, O. Etesami, N. Immorlica and M. Mahdian)
2nd
Workshop on Sponsored Search Auctions (2006) and
Proceedings of the 16th international conference on World Wide Web (WWW), 531-540 (2007). |
|
|
Local computation of pagerank contributions
(with R. Andersen, , J. T. Chayes., J. Hopcroft, V. Mirrokni and S. Teng)
Proceedings of the 5th Workshop on Algorithms and Models for
the Web Graph (WAW), 150-165 (2007).
|
|
|
The myth of the folk theorem
(with J. T. Chayes, N. Immorlica, A. Kalai, V. Mirrokni
and C. Papadimitriou)
Proceedings of the 40st Annual ACM Symposium on the Theory of Computing (STOC) ,
365-372 (2008).
|
|
|
Trust-based recommendation systems: An axiomatic approach
(with R. Andersen, J. T. Chayes, U.Feige, A. Flaxman, A. Kalai, V. Mirrokni and M. Tennenholtz)
Proceedings of the 17th international conference on World Wide Web (WWW), 199-208 (2008).
|
|
|
Robust PageRank and locally computable spam detection features
(with R. Andersen, J. T. Chayes, J. E. Hopcroft, K. Jain, V.S. Mirrokni and S.H. Teng)
AIRWeb 2008, 69-76 (2008).
|
|
|
On the Stability of Web Crawling and Web Search
(with R. Andersen, J. T. Chayes, J. E. Hopcroft, V.S. Mirrokni and S.H. Teng)
ISAAC 2008, 680-691 (2008).
|
Monte Carlo Markov Chains
|
|
Torpid mixing of some Monte Carlo Markov Chain algorithms in statistical physics
(with J. T. Chayes, A. Frieze, J.H. Kim, P. Tetali, E. Vigoda and V. Vu)
Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS),
218-229 (1999).
|
|
|
On the sampling problem for H-colorings on the hypercubic lattice
(with J. T. Chayes, M. Dyer and P. Tetali)
in Graphs, Morphisms and Statistical Physics (eds. J Nesetril and P Winkler),
DIMACS Series in Discrete Mathematics and Theoretical Computer Science 63,
13-28, American Mathematical Society (2004). |
Zeros of Complex Partition Functions and Lee-Yang Theory
|
|
Gibbs states of graphical representations of the Potts model with external fields
(with M. Biskup, J. T. Chayes and R. Kotecky)
Journal of Mathematical Physics 41, 1170-1210 (2000).
|
|
|
General theory of Lee-Yang zeros in models with first-order phase transitions
(with M. Biskup, J. T. Chayes, L. Kleinwaks and R. Kotecky)
Physical Review Letters 84, 4794-4797 (2000).
|
|
|
Partition function zeros at first-order phase transitions: A general analysis
(with M. Biskup, J. T. Chayes, L. Kleinwaks and R. Kotecky)
Communications in Mathematical Physics 251, 79-131 (2004). |
|
|
Partition function zeros at first-order phase transitions:
Piorogov-Sinai theory
(with M. Biskup, J. T. Chayes and R. Kotecky)
Journal of Statistical Physics 116, 97-155 (2004).
|
|
|
Absence of Zeros for the Chromatic Polynomial on Bounded Degree Graphs Combinatorics, Probability and Computing
15, 63-74 (2006).
|
