Jennifer Chayes
Microsoft
The Power of Locality for Network Algorithms
Abstract: Given the massive size of most networks of interest, conventional network algorithms — which typically scale as polynomials in the network size — are woefully inadequate in practice. In the first part of this talk, we consider a host of questions which are either explicitly local or can be approximated by local questions: pagerank, coverage, diffusion, determining the most influential nodes. We show how to use locality to deliver much more efficient algorithms (quasilinear or even sublinear in the network size), though sometimes at the expense of a degradation in the approximation relative to optimal algorithms. In the second part of this talk, we consider another aspect of locality, namely the question of local data access. Many large networks are encoded locally, e.g., with adjacency lists. How does the nature of the data access impact the efficiency of algorithms? Surprisingly, we show that small differences in data access can lead to very large differences in efficiency and approximability of network algorithms. As an example, we consider a covering problem which arises naturally for recruiters on social networks, and show how small differences between the information on neighbors in LinkedIn and Facebook lead to large differences in their usefulness to recruiters.
Biography: Jennifer Tour Chayes is Distinguished Scientist and Managing Director of Microsoft Research New England in Cambridge, Massachusetts, which she co-founded in 2008, and Microsoft Research New York City, which she co-founded in 2012. Chayes was Research Area Manager for Mathematics, Theoretical Computer Science and Cryptography at Microsoft Research Redmond until 2008. 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.
Chayes received her BA in biology and physics at Wesleyan University, where she graduated first in her class, and her PhD 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. Chayes has recently been the recipient of many leadership awards including the Leadership Award of Women Entrepreneurs in Science and Technology, the Leading Women Award of the Girl Scouts of Eastern Massachusetts, the Women to Watch Award of the Boston Business Journal, and the Women of Leadership Vision Award of the Anita Borg Institute. 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, the Fields Institute, and the Association for Computing Machinery, 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. She is also one of the world’s experts in the modelling 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.
Did you miss Jennifer Chayes's lecture or would you like to hear it again? If so, just start the video below.
