Christian Borgs
Christian
Borgs is the deputy managing director of
Microsoft Research New England in
Cambridge, Massachusetts.
He studied physics at the
University of Munich, the
University Pierre et Marie Curie in Paris, the
Institut des Hautes Etudes in
BuressurYvettes, and the
MaxPlanckInstitute 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 cofound the Theory Group.
He was a manager of the Theory group until 2008, when he cofounded Microsoft Research New England.
Christian Borgs is well known for
his work on the mathematical theory of
firstorder phase transitions and finitesize effects, for
which he won the 1993 KarlScheel 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 selforganized networks (such as the
Internet, the World Wide Web and social networks), as well as the analysis of
processes and algorithms on networks. His current interests include the following areas:
 graph theory, structural
and dynamical properties of networks
 mathematical theory of growing graphs
sequences
 algorithmic game theory and
recommendation systems
 phase transitions in
combinatorics and theoretical computer science
 belief propagation and
applications in systems biology
 analysis of Monte Carlo
Markov chains

His most recent research includes game
theoretic models of online social networks, the development of pricing algorithms to incentivize energy
conservation in cloud computing, the analysis of local graph algorithms, and the development of methods to reconstruct gene regulatory
networks in order to find potential drug targets for cancer treatment.
On the more mathematical side, he has been one of the founders of the area of
convergent graphs sequences, a field which characterizes the properties of sequences of growing networks
and studies the properties of their limiting structures.
Christian Borgs has authored
about 120 research papers and is named as an inventor on a litle over 30 patents. Among the honors he has
received are a scholarship from the
German National Merit Foundation,
the above mentioned
KarlScheel 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 longterm 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 or is still serving 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,
the
Annales de l'Institut Henri Poincaré D
,
the Board of Trustees
of the Institute for Pure and Applied Mathematics (IPAM),
and the governing board of
the Institute for Mathematics and its Applications.
He is a fellow of the
American Mathematical Society,
and the
Association of the Advancement of Science.
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)
Network
Modeling and Graph Theory

Directed scalefree graphs
(with B. Bollobas, J. T. Chayes and O. Riordan)
Proceedings of the 14th Annual ACMSIAM Symposium on Discrete Algorithms (SODA),
132139 (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), 725738, 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), 783787 (2004).


Newsgroup cluster data referred to in the above paper.


Competitioninduced 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), 208221, Lecture Notes in Computer Science 3142 (2004). 

Degree distribution of competitioninduced preferential attachment
graphs
(with N. Berger, J. T. Chayes, R. D'Souza and R. D. Kleinberg)
Combinatorics, Probability and Computing 14, 697721 (2005). 

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, 61126117 (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), 135144 (2007).

Convergent Graph Sequences

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),
315371, Springer (2006). 

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),
261270 (2006).


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, 18011851 (2008).


Convergent sequences of dense graphs II: Multiway cuts and statistical physics
(with J. T. Chayes, L. Lovasz, V. Sos, and K. Vesztergombi) Ann.
of Math. 176, 151219 (2012).


Moments of twovariable functions and the uniqueness of graph limits
(with J. T. Chayes and L. Lovasz)
GAFA 19, 15971619 (2010).


Limits of randomly grown graph sequences
(with J. T. Chayes, L. Lovasz, V. Sos, K. Veszterbombi)
Eur. J. Comb. 32, 985999 (2011).


Left and right convergence of graphs with bounded degree
(with J. T. Chayes, J. Kahn, L. Lovasz)
Random Struct. Alg. 42, 128 (2013). 

Asymptotic behavior and distributional limits of preferential attachment graphs
(with N. Berger, J. T. Chayes, A. Saberi)
Ann. Probab. 42(1), 140 (2014).


Convergent sequences of sparse graphs: A large deviations approach
(with J. T. Chayes and D. Gamarnik)
preprint (2013). 

An L^{p} theory of sparse graph convergence I:
limits, sparse random graph models, and power law distributions
(with J. T. Chayes, H. Cohn and Y. Zhao)
preprint (2014). 

An L^{p} theory of sparse graph convergence II:
LD convergence, quotients, and right convergence
(with J. T. Chayes, H. Cohn and Y. Zhao)
preprint (2014). 
Processes on Networks and Graph Algorithms

On the spread of viruses on the Internet
(with N. Berger, J. T. Chayes and A. Saberi)
Proceedings of the 16th ACMSIAM Symposium on Discrete Algorithm (SODA), 301310 (2005). 

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), 150165 (2007).


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, 6976 (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, 680691 (2008).


How to distribute antidote to control epidemics
(with J. T. Chayes, A. Ganesh, and A. Saberi)
Random Struct. Algorithms 37, 204222 (2010).


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), 517526 (2011).


A sublinear time algorithm for PageRank computations
(with M. Brautbar, J.T. Chayes and S.H. Teng)
Proceedings of the 9th Workshop
on Algorithms and Models for the Web Graph (WAW), 4153 (2012).


The power of local information in social networks
(with M. Brautbar, J. Chayes, S. Khanna, B. Lucier)
Proceedings of the 8th International Workshop on Internet and Network Economics
(WINE), 406  419 (2012). 

Finding endogenously formed communities
(with M.F. Balcan, M. Braverman, J.T. Chayes and S.H. Teng)
24th Annual ACMSIAM Symposium on Discrete Algorithm (SODA), 767783 (2013). 

MultiScale Matrix Sampling and SublinearTime PageRank
(with M. Brautbar, J.T. Chayes and S.H. Teng)
Internet Mathematics 10, 2048 (2014).


Maximizing social influence in nearly optimal time
(with M. Brautbar, J. Chayes and B. Lucier)
Proceedings of the 25nd Annual ACMSIAM
Symposium on Discrete Algorithm (SODA), 946957 (2014).

Game Theory,
Auctions and Recommendation Systems

Multiunit auctions with budgetconstrained bidders
(with J. T. Chayes, N. Immorlica, M. Mahdian and A. Saberi)
Proceedings of the 6th ACM Conference on Electronic Commerce (EC), 4451 (2005). 

Bid optimization in online advertisement auctions
(with J. T. Chayes, O. Etesami, N. Immorlica and M. Mahdian)
2^{nd}
Workshop on Sponsored Search Auctions (2006) and
Proceedings of the 16th international conference on World Wide Web (WWW), 531540 (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) ,
365372 (2008).


Trustbased 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), 199208 (2008).


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) 87105 (2010).


Gametheoretic models of information overload in social networks
(with J. T. Chayes, B. Karrer, B. Meeder, R. Ravi, R. Reagans and A. Sayedi)
Proceedings of the 7th Workshop on Algorithms and Models for the Web Graph (WAW) 146  161 (2010).


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 ACMSIAM Symposium on Discrete Algorithm
(SODA), 15181537 (2011).


The hitchhiker's guide to affiliation networks: A gametheoretic approach
(with J. T. Chayes, J. Ding and B. Lucier)
Proceedings of the 2nd
Symposium on Innovations in Computer Science (ICS), 389400 (2011).


Pricing and queuing
(with J.T. Chayes, S. Doroudi, M. HarcholBalter, K. Xu)
ACM SIGMETRICS Performance Evaluation Review 40(3): 7173 (2012).


Optimal multiperiod pricing with service guarantees
(with O. Candogan,
J.T. Chayes, I. Lobel, and H. Nazerzadeh)
Management Science 60, 17921811 (2014).


Priority pricing in queues with a continuous distribution of customer valuations
(S. Doroudi, M. Akan, M. HarcholBalter, J. Karp, C. Borgs, J.T. Chayes)
Preprint 2013. 

The optimal admission threshold in observable
queues with state dependent pricing
(with J.T. Chayes, S. Doroudi, M. HarcholBalter, K. Xu)
Probability in the Engineering and Informational Sciences 28, 101110 (2014). 

Bargaining dynamics in exchange networks
(with M. Bayati, J.T. Chayes,
Y. Kanoria and A. Montanari), to appear in J. Econ. Theory,
http://dx.doi.org/10.1016/j.jet.2014.02.007,
(2014).

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, 368413 (1999).


The birth of the infinite cluster: Finitesize scaling in percolation
(with J. T. Chayes, H. Kesten and J. Spencer)
Communications in Mathematical Physics 224, 153204 (2001).


The scaling window of the 2SAT transition
(with B. Bollobas, J. T. Chayes, J.H. Kim and D.B. Wilson)
Random Structures and Algorithms 18, 201256 (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), 330336 (2001).


Phase transition and finitesize scaling for the integer partitioning problem
(with J. T. Chayes and B. Pittel)
Random Structures and Algorithms 19, 247288 (2001).


Constrained integer partitions
(with J. T. Chayes, S. Mertens and B. Pittel)
Proceedings of the 6th Latin American Symposium on Theoretical Information
(LATIN), 5968, 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, 315380 (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, 137184 (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, 18861944 (2005). 

Random subgraphs of finite graphs: III. The phase transition
for the ncube
(with J. T. Chayes, R. van der Hofstad, G. Slade and J. Spencer)
Combinatorica 26, 395410 (2006). 

The KestenStigum 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),
518530 (2006).


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, 217240 (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, 241284 (2009).


Percolation on dense graph sequences
(with B. Bollobas, J. T. Chayes and O. Riordan)
Ann. Probab. 38, 150183 (2010).

Belief Propagation
and Applications in Systems Biology

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


BeliefPropagation for weighted bmatchings 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, 9891011 (2011).


Finding undetected protein associations in cell signaling by belief propagation
(with M. BaillyBechet, A. Braunstein, J. Chayes, A.Dagkessamanskaia,
J. Francois, and R. Zecchina). Proceedings of the National Academy of Sciences
(PNAS) 108, 882887 (2011).


Simultaneous reconstruction of multiple signaling pathways via the
prizecollecting Steiner forest problem
(N.Tuncbag, A.Braunstein, A.Pagnani, S.C.Huang, J.Chayes, C.Borgs, R.Zecchina, E.Fraenkel),
16th Annual International Conference on Research in Computational Molecular Biology (RECOMB), 287  301 (2012)
and Journal of Computational Biology 20, 124136 (2013).


Sharing information to reconstruct patientspecific pathways in heterogeneous diseases
(A. Gitter, A. Braunstein, A. Pagnani, C. Baldassi, C. Borgs, J. Chayes, R. Zecchina, E. Fraenkel)
Proceedings of the Pacific Symposium on Biocomputing, 3950 (2014).

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),
218229 (1999).


On the sampling problem for Hcolorings 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,
1328, American Mathematical Society (2004).


Tight bounds for mixing of the SwendsenWang algorithm at the Potts transition point
(with J. T. Chayes and P. Tetali), Probab. Theory Relat. Fields 152, 509  557
(2012). 
Zeros of Complex Partition Functions and LeeYang 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, 11701210 (2000).


General theory of LeeYang zeros in models with firstorder phase transitions
(with M. Biskup, J. T. Chayes, L. Kleinwaks and R. Kotecky)
Physical Review Letters 84, 47944797 (2000).


Partition function zeros at firstorder phase transitions: A general analysis
(with M. Biskup, J. T. Chayes, L. Kleinwaks and R. Kotecky)
Communications in Mathematical Physics 251, 79131 (2004). 

Partition function zeros at firstorder phase transitions:
PiorogovSinai theory
(with M. Biskup, J. T. Chayes and R. Kotecky)
Journal of Statistical Physics 116, 97155 (2004).


Absence of zeros for the chromatic polynomial on bounded degree graphs
Combinatorics, Probability and Computing
15, 6374 (2006).

Some Earlier Work in Statistical Physics and
Lattice Gauge Theory

Lattice YangMills theory at nonzero temperatures and the confinement problem
(with E. Seiler)
Commun. Math. Phys. 91, 329380 (1983).


Confinement, deconfinement and freezing in lattice Yang  Mills theories with continuous time
Commun. Math. Phys. 116, 309342 (1988).


A unified approach to phase diagrams in field theory and statistical mechanics
(with J. Imbrie)
Commun. Math. Phys. 128, 305328 (1988).


A rigorous theory of finitesize scaling at firstorder phase transitions
(with R. Kotecky)
J. Stat. Phys. 61, 79  110 (1990).


Finitesize scaling for Potts models
(with R. Kotecky and S. MiracleSole)
J. Stat. Phys. 62, 529  551 (1991). 

A new method to determine firstorder transition points from finitesize data
(with W. Janke)
Phys. Rev. Lett. 68, 1738  1741 (1992).


Finitesize scaling and surface tension from effective onedimensional systems
(with J. Imbrie) Commun. Math. Phys. 145, 235280 (1992)


Finitesize scaling for Potts models in long cylinders.
Nucl. Phys. B384, 605645 (1992).


Crossoverfinitesize scaling at first order transitions
(with J. Imbrie)
J. Stat. Phys. 69, 487537 (1992).


Low temperature phase diagrams for quantum perturbations of classical spin systems
(with R. Kotecky, D. Ueltschi). Commun. Math. Phys. 181, 409446 (1996).
