Jennifer Tour Chayes

Jennifer Tour Chayes is managing director of the newly announced Microsoft Research New England lab in Cambridge, Massachusetts, scheduled to open in July 2008.  Before this, she was research area manager for Mathematics, Theoretical Computer Science and Cryptography at Microsoft Research Redmond.  Chayes joined Microsoft Research in 1997, when she co-founded the Theory Group.  Her research areas include phase transitions in discrete mathematics and computer science, structural and dynamical properties of self-engineered networks, and algorithmic game theory.  She is the co-author of almost 100 scientific papers and the co-inventor of more than 20 patents.     Chayes has many ties to the academic community.  She is Affiliate Professor of Mathematics and Physics at the University of Washington, and was for many years Professor of Mathematics at UCLA.  She serves on numerous institute boards, advisory committees and editorial boards, including the Turing Award Selection Committee of the Association for Computing Machinery, the Board of Trustees of the Mathematical Sciences Research Institute, the Advisory Boards of the Center for Discrete Mathematics and Computer Science and the Miller Institute for Basic Research in Science, the U.S. National Committee for Mathematics and the Committee on Assuring the Integrity of Research Data of the National Academies, the Advisory Committee on Women in Computing of the Association for Computing Machinery, the Leadership Advisory Council of the Anita Borg Institute for Women and Technology, and the Selection Committee for the Anita Borg Award for Technical Leadership.  Chayes is a past Chair of the Mathematics Section of the American Association for the Advancement of Science, and a past Vice-President of the American Mathematical Society.     Chayes received her B.A. in biology and physics at Wesleyan University, where she graduated first in her class, and her Ph.D. in mathematical physics at Princeton.  She did her postdoctoral work in the mathematics and physics departments at Harvard and Cornell.  She is the recipient of a National Science Foundation Postdoctoral Fellowship, a Sloan Fellowship, and the UCLA Distinguished Teaching Award.  She has twice been a member of the Institute for Advanced Study in Princeton.  Chayes is a Fellow of the American Association for the Advancement of Science, and a National Associate of the National Academies.     Chayes is best known for her work on phase transitions, in particular for laying the foundation for the study of phase transitions in problems in discrete mathematics and theoretical computer science; this study is now giving rise to some of the fastest known algorithms for fundamental problems in combinatorial optimization.  She is also one of the world’s experts in the modeling and analysis of random, dynamically growing graphs – which are used to model the Internet, the World Wide Web and a host of other technological and social networks.  Among Chayes’ contributions to Microsoft technologies are the development of methods to analyze the structure and behavior of various networks, the design of auction algorithms, and the design and analysis of various business models for the online world.     Chayes lives with her husband, Christian Borgs, who also happens to be her principal scientific collaborator.  In her spare time, she enjoys overworking.

Selected Publications

Phase Transitions in Combinatorics and Computer Science

	Uniform boundedness of crossing probabilities implies hyperscaling (with C. Borgs, 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 C. Borgs, H. Kesten and J. Spencer) Communications in Mathematical Physics 224, 153-204 (2001).
	The scaling window of the 2-SAT transition (with B. Bollobas, C. Borgs, 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 C. Borgs 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 C. Borgs and B. Pittel) Random Structures and Algorithms 19, 247-288 (2001).
	Constrained integer partitions (with C. Borgs, 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 C. Borgs, 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 C. Borgs, 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 C. Borgs, 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 C. Borgs, R. van der Hofstad, G. Slade and J. Spencer) Combinatorica 26, 395-410 (2006).
	Proof of the local REM conjecture for number partitioning I: Constant energy scales (with C. Borgs, S. Mertens and C. Nair) Preprint (2005).
	Proof of the local REM conjecture for number partitioning II: Growing energy scales (with C. Borgs, S. Mertens and C. Nair) Preprint (2005).
	The Kesten-Stigum reconstruction bound is tight for roughly symmetric binary channels (with C. Borgs, 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, C. Borgs and O. Riordan) Preprint (2007).

Networks and Graph Theory

	Directed scale-free graphs (with B. Bollobas, C. Borgs 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, C. Borgs 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 C. Borgs, 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, C. Borgs, 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, C. Borgs, 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, C. Borgs and A. Saberi) Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithm (SODA), 301-310 (2005).
	Graph limits and parameter testing (with C. Borgs, 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 C. Borgs, 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 C. Borgs, L. Lovasz, V. Sos, and K. Vesztergombi) Preprint (2006).
	Convergent sequences of dense graphs II: Multiway Cuts and Statistical Physics (with C. Borgs, L. Lovasz, V. Sos, and K. Vesztergombi) Preprint (2007).
	Emergence of tempered preferential attachment from optimization (with N. Berger, C. Borgs, 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 C. Borgs, C. Daskalakis and S.Roch) Proceedings of the 39rd annual ACM Symposium on the Theory of Computing (STOC), 135-144 (2007).

Algorithmic Game Theory and Recommendation Systems

Multi-unit auctions with budget-constrained bidders (with C. Borgs, 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 C. Borgs, 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 C. Borgs, N. Immorlica, A. Kalai, V. Mirrokni and C. Papadimitriou) Proceedings of the 40st Annual ACM Symposium on the Theory of Computing (STOC) (2008).
	Local computation of pagerank contributions (with R. Andersen, C. Borgs, J. Hopcroft, V. Mirrokni and S. Teng) Proceedings of the  5th Workshop on Algorithms and Models for the Web Graph (WAW), 150-165 (2007).
	Trust-based recommendation systems: An axiomatic approach (with R. Andersen, C. Borgs, U.Feige, A. Flaxman, A. Kalai, V. Mirrokni and M. Tennenholtz) Proceedings of the 17th international conference on World Wide Web (WWW) (2008).

Monte Carlo Markov Chains

	Torpid mixing of some Monte Carlo Markov Chain algorithms in statistical physics (with C. Borgs, 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 C. Borgs, 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, C. Borgs 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, C. Borgs, 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, C. Borgs, 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, C. Borgs and R. Kotecky) Journal of Statistical Physics 116, 97-155 (2004).