Source: http://christianborgs.com/
Timestamp: 2019-04-20 14:20:52+00:00

Document:
Christian Borgs is co-founder and deputy managing director of Microsoft Research New England in Cambridge, Massachusetts.
His recent research includes the analysis of local graph algorithms, game theoretic models of online social networks, and the development of methods to reconstruct gene regulatory networks for cancer. He is one of the inventors of the field of limits of graph sequences (graphons), which are now being used in the machine learning of non-parametric models for large sparse networks, as well as the development of recommendation systems when the matrix of known recommendations is very sparse. He has also started to work on privacy, as well as fairness and accountability in machinge learning.
Christian Borgs has authored almost 140 research papers and is named as coinventor of over 30 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 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), the Governing Board of the Institute for Mathematics and its Applications (IMA), the Adivosry Board of the Harvard Insitute for Applied Computer Science (IACS) and the External Advisory Board for Computing at NYU. He has been chair of Board of Governors of the IMA from 2017-2018, and is currently past chair of that board. Christian Borgs 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.
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).
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).
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).
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, 151-219 (2012).
Moments of two-variable functions and the uniqueness of graph limits (with J. T. Chayes and L. Lovasz). GAFA 19, 1597-1619 (2010).
Limits of randomly grown graph sequences (with J. T. Chayes, L. Lovasz, V. Sos, K. Veszterbombi). Eur. J. Comb. 32, 985-999 (2011).
Left and right convergence of graphs with bounded degree (with J. T. Chayes, J. Kahn, L. Lovasz). Random Struct. Alg. 42, 1-28 (2013).
Asymptotic behavior and distributional limits of preferential attachment graphs (with N. Berger, J. T. Chayes, A. Saberi). Ann. Probab. 42(1), 1-40 (2014).
An Lp 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), to appear in Transactions of the AMS.
An Lp theory of sparse graph convergence II: LD convergence, quotients, and right convergence (with J. T. Chayes, H. Cohn and Y. Zhao). Annals of Prob. 45, 337-396 (2018).
Graphons: A nonparametric method to model, estimate, and design algorithms for massive networks (with J. T. Chayes). Proceedings of the 18th ACM Conference on Economics and Computation (EC�17), 665�672, (2017).
Sparse exchangeable graphs and their limits via graphon processes (with J. T. Chayes, H. Cohn and N. Holden). Journal of Machine Learning Research 18 (210), 1-71 (2018).
Sampling perspectives on sparse exchangeable graphs (with J.T. Chayes, H. Cohn, V. Veitch). Preprint (2017).
Identifiability for graphexes and the weak kernel metric (with J.T. Chayes, H. Cohn, L. M. Lovasz). Preprint (2018).
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).
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).
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).
Game-theoretic 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 ACM-SIAM Symposium on Discrete Algorithm (SODA), 1518-1537 (2011).
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).
Pricing and queuing (with J.T. Chayes, S. Doroudi, M. Harchol-Balter, K. Xu). ACM SIGMETRICS Performance Evaluation Review 40(3): 71-73 (2012).
Priority pricing in queues with a continuous distribution of customer valuations (S. Doroudi, M. Akan, M. Harchol-Balter, J. Karp, C. Borgs, J.T. Chayes). CMU technical report CMU-CS-13-109 (2013).
The optimal admission threshold in observable queues with state dependent pricing (with J.T. Chayes, S. Doroudi, M. Harchol-Balter, K. Xu). Probability in the Engineering and Informational Sciences 28, 101-110 (2014).
Optimal multi-period pricing with service guarantees (with O. Candogan, J.T. Chayes, I. Lobel, and H. Nazerzadeh). Management Science 60, 1792-1811 (2014).
An axiomatic approach to community detection (with C. Borgs, A. Marple, and S.-H. Teng). Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science (ITCS '16), 135-146 (2016).
Thy friend is my friend: iterative collaborative filtering for sparse matrix estimation (with J.T. Chayes, C.E. Lee, D.Shah). Advances in Neural Information Processing Systems (NIPS) 30, 4718�4729, (2017).
Iterative collaborative filtering for sparse matrix estimation (with J.T. Chayes, C.E. Lee, D.Shah). Preprint (2017).
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).
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).
Private graphon estimation for sparse graphs (with J. T. Chayes and A. Smith). Advances in Neural Information Processing Systems (NIPS) 28, 1369--1377 (2015).
Consistent nonparametric estimation for heavy-tailed sparse graphs (with J. T. Chayes, H. Cohn and S. Ganguly). Preprint (2015).
Unreasonable effectiveness of learning neural networks: From accessible states and robust ensembles to basic algorithmic schemes (with C. Baldassi, J. T. Chayes, A. Ingrosso, C. Lucibello, L. Saglietti, and R. Zecchina). Proceedings of the National Academy of Sciences (PNAS) 113, E7655�E7662 (2016).
Revealing network structure, condentially: improved rates for node private graphon estimation (with J.T. Chayes, A. Smith, I. Zadik). Proceedings of the 59 th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 533-543 (2018).
What�s in a name? Reducing bias in bios without access to protected attributes. (A. Romanov, M. De-Arteaga, H. Wallach, J. Chayes, C. Borgs, A. Chouldechova, S. Geyik, K. Kenthapadi, A. Kalai). Proceedings of the 2019 Annual Conference of the North American Chapter of the Association for Computational Linguistics (NAACL '19). Best paper award.
Algorithmic greenlining: an approach to increase diversity (with J. Chayes, N. Haghtalab, A. Kalai and E. Vitercik). AIII / ACM Conference on Artificial Intelligence, Ethics and Society (AIES) 13pp, (2019).
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).
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). 16th Annual International Conference on Research in Computational Molecular Biology (RECOMB), 287 - 301 (2012) and Journal of Computational Biology 20, 124-136 (2013).
A multifactorial model of T cell expansion and durable clinical benefit in response to a PD-L1 inhibitor (M. Leiserson, V. Syrgkanis, A. Gilson, M. Dudik, S. Gillett, J. Chayes, C. Borgs, D.F. Bajorin, J. Rosenberg, S. Funt, A. Snyder, L. Mackey). PLoS ONE 13(12): e0208422, (2018).
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).
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).
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).
How to distribute antidote to control epidemics (with J. T. Chayes, A. Ganesh, and A. Saberi). Random Struct. Algorithms 37, 204-222 (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), 517-526 (2011).
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).
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), 41-53 (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 ACM-SIAM Symposium on Discrete Algorithm (SODA), 767-783 (2013).
Multi-scale matrix sampling and sublinear-time PageRank (with M. Brautbar, J.T. Chayes and S.-H. Teng). Internet Mathematics 10, 20-48 (2014).
Maximizing social influence in nearly optimal time (with M. Brautbar, J. Chayes and B. Lucier). Proceedings of the 25nd Annual ACM-SIAM Symposium on Discrete Algorithm (SODA), 946-957 (2014).
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).
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).
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.
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).
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).
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).
Percolation on dense graph sequences (with B. Bollobas, J. T. Chayes and O. Riordan). Ann. Probab. 38, 150-183 (2010).
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).
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 152, 509 - 557 (2012).
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).
Lattice Yang-Mills theory at nonzero temperatures and the confinement problem (with E. Seiler). Commun. Math. Phys. 91, 329-380 (1983).
Confinement, deconfinement and freezing in lattice Yang - Mills theories with continuous time Commun. Math. Phys. 116, 309-342 (1988).
A unified approach to phase diagrams in field theory and statistical mechanics (with J. Imbrie). Commun. Math. Phys. 128, 305-328 (1988).
A rigorous theory of finite-size scaling at first-order phase transitions (with R. Kotecky). J. Stat. Phys. 61, 79 - 110 (1990).
Finite-size scaling for Potts models (with R. Kotecky and S. Miracle-Sole). J. Stat. Phys. 62, 529 - 551 (1991).
A new method to determine first-order transition points from finite-size data (with W. Janke). Phys. Rev. Lett. 68, 1738 - 1741 (1992).
Finite-size scaling for Potts models in long cylinders. Nucl. Phys. B384, 605-645 (1992).
Crossover-finite-size scaling at first order transitions (with J. Imbrie). J. Stat. Phys. 69, 487-537 (1992).
Low temperature phase diagrams for quantum perturbations of classical spin systems (with R. Kotecky, D. Ueltschi). Commun. Math. Phys. 181, 409-446 (1996).

References: V. 
 V. 
 V. 
 V. 
 V. 
 V. 
 V. 
 V. 
 V. 
 V. 
 V.