Share this page
  • Share this page on Twitter Share this page on Facebook Share this page on Digg Share this page on Del.icio.us Read the Inside Microsoft Research blog
  • E-mail this page Print this page
  • RSS feeds
Home  > People > Christian Borgs
Christian Borgs

Picture of Christian BorgsChristian Borgs is the deputy managing director of Microsoft Research New England in Cambridge, Massachusetts, as well as an affiliate professor of mathematics at the University of Washington.  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 was a manager of the Theory group until 2008, when he co-founded Microsoft Research New England.

Christian Borgs 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.  His current interests include the following areas:

 
  • graph theory, structural and dynamical properties of networks
  • algorithmic game theory and recommendation systems
  • belief propagation
  • analysis of Monte Carlo Markov chains
  • phase transitions in combinatorics and theoretical computer science
His most recent research includes game theoretic models of online social networks, the development of pricing algorithms to incentivize energy conservation in cloud computing, and the development of methods to reconstruct gene regulatory networks in order to find potential drug targets for cancer treatment.

Christian Borgs is the co-author of about 100 research papers and he 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 been invited by the Conference Board of Mathematical Sciences (CBMS) to give a lecture series on "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, the SIAM Journal on Discrete Mathematics, the Journal of Statistical Mechanics, 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 (see here for the complete list)

Networks and Graph Theory

PDF 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).
PDF 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).
PDF 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).
DATA Newsgroup cluster data referred to in the above paper.
PDF 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).
PDF 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).
PDF 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).
PDF 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).
PDF 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).
PDF 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.
PDF Fitting the WHOIS Internet data A short note with technical details left out in the above paper.
PDF 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).
PDF Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testing (with J. T. Chayes, L. Lovasz, V. Sos, and K. Vesztergombi) Advances in Math. 219, 1801-1851 (2008).
PDF How to distribute antidote to control epidemics (with J. T. Chayes, A. Ganesh, and A. Saberi) Random Struct. Algorithms 37, 204-222 (2010).
PDF Moments of two-variable functions and the uniqueness of graph limits (with J. T. Chayes and L. Lovasz) GAFA 19, 1597-1619 (2010).
PDF Limits of randomly grown graph sequences (with J. T. Chayes, L. Lovasz, V. Sos, K. Veszterbombi) Eur. J. Comb. 32, 985-999 (2011).
PDF Left and right convergence of graphs with bounded degree (with J. T. Chayes, J. Kahn, L. Lovasz) preprint (2010).
PDF A weak distributional limit for preferential attachment graphs (with N. Berger, J. T. Chayes, A. Saberi) preprint (2010).
PDF Convergent sequences of dense graphs II: Multiway cuts and statistical physics (with J. T. Chayes, L. Lovasz, V. Sos, and K. Vesztergombi) To appear in Ann. of Math. (2011).

Game Theory, Auctions and Recommendation Systems

PDF 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).
PDF 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).
PDF 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).
PDF 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).
PDF 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).
PDF 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).
PDF 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).
PDF A novel approach to propagating distrust (with J. T. Chayes, A. Kalai, A. Malekiany, M. Tennenholtz) Proceedings of the 6th International Workshop on Internet and Network Economics (WINE) 87-105 (2010).
PDF Game-theoretic models of information overload in social networks (with J. T. Chayes, B. Karrer, B. Meeder, R. Ravi, R. Reagans and A. Sayedi) to appear in the 7th Workshop on Algorithms and Models for the Web Graph (WAW 2010).
PDF Fast convergence of natural bargaining dynamics in exchange networks (with Y. Kanoria, M. Bayati, J. T. Chayes, and A. Montanari) Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithm (SODA), 1518-1537 (2011).
PDF The hitchhiker's guide to affiliation networks: A game-theoretic approach (with J. T. Chayes, J. Ding and B. Lucier) Proceedings of the 2nd Symposium on Innovations in Computer Science (ICS), 389-400 (2011).
PDF We know who you followed last summer: inferring social link creation times in twitter (with B. Meeder, B. Karrer, A. Sayedi, R. Ravi and J.T. Chayes). Proceedings of the 20th International World Wide Web Conference (WWW), 517-526 (2011).
PDF Optimal multi-period pricing with service guarantees (with O. Candogan, J.T. Chayes, I. Lobel, and H. Nazerzadeh) Preprint (2011).
PDF Bargaining dynamics in exchange networks (with M. Bayati, J.T. Chayes, Y. Kanoria and A. Montanari) Preprint (2011).
PDF Sublinear time algorithm for PageRank computations and related applications (with M. Brautbar, J.T. Chayes and S.-H. Teng), to appear in the 9th Workshop on Algorithms and Models for the Web Graph (WAW 2012).
PDF Finding endogenously formed communities (with M.-F. Balcan, M. Braverman, J.T. Chayes and S.-H. Teng) Preprint (2012).
PDF The power of local information in social networks (with M. Brautbar, J. Chayes, S. Khanna, B. Lucier) Preprint (2012).

Belief Propagation and Applications in Systems Biology

PDF Statistical mechanics of Steiner trees (with M. Bayati, A. Braunstein, J. Chayes, A. Ramezanpour, and R. Zecchina) Physical Review Letters 101, 037208 (2008), reprinted in Virtual Journal of Biological Physics Research 16, August 1 (2008).
PDF Belief-Propagation for weighted b-matchings on arbitrary graphs and its relation to linear programs with integer solutions (with M. Bayati, J. Chayes and R. Zecchina) SIAM Journal of Discrete Mathematics 25, 989-1011 (2011).
PDF Finding undetected protein associations in cell signaling by belief propagation (with M. Bailly-Bechet, A. Braunstein, J. Chayes, A.Dagkessamanskaia, J. Francois, and R. Zecchina). Proceedings of the National Academy of Sciences (PNAS) 108, 882-887 (2011).
Empty Simultaneous reconstruction of multiple signaling pathways via the prize-collecting Steiner forest problem (N.Tuncbag, A.Braunstein, A.Pagnani, S.C.Huang, J.Chayes, C.Borgs, R.Zecchina, E.Fraenkel), submitted, (2011).

Monte Carlo Markov Chains

PDF 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).
PDF 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).
PDF Tight bounds for mixing of the Swendsen-Wang algorithm at the Potts transition point (with J. T. Chayes and P. Tetali), Probab. Theory Relat. Fields, Online First, 1-49 (2010).

Phase Transitions in Combinatorics and Computer Science

PDF Uniform boundedness of crossing probabilities implies hyperscaling (with J. T. Chayes, H. Kesten and J. Spencer) Random Structures and Algorithms 15, 368-413 (1999).
PDF 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).
PDF 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).
PDF 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).
PDF 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).
PDF 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).
PDF 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).
PDF 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).
PDF 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).
PDF 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).
PDF 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).
PDF 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).
PDF 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).
PDF Percolation on dense graph sequences (with B. Bollobas, J. T. Chayes and O. Riordan) Ann. Probab. 38, 150-183 (2010).

Zeros of Complex Partition Functions and Lee-Yang Theory

PDF 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).
PDF 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).
PDF 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).
PDF 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).
PDF Absence of zeros for the chromatic polynomial on bounded degree graphs Combinatorics,  Probability and Computing 15, 63-74 (2006).