We review belief propagation algorithms inspired by the study of phase transitions in combinatorial optimization problems. In particular, we present rigorous results on convergence of such algorithms for matching and associated bargaining problems on networks. We also present a belief propagation algorithm for the prize- collecting Steiner tree problem, for which rigorous convergence results are not yet known. Finally, we show how this algorithm can be used to discover pathways in cancer genomics, and to suggest possible drug targets for cancer therapy. These methods give us the ability to share information across multiple patients to help reconstruct highly patient-specific networks.
Jennifer Chayes (Microsoft Research)
Jennifer Chayes is Technical Fellow and Managing Director of Microsoft Research New England, New York City, and Montreal. She was for many years Professor of Mathematics at UCLA. She is author of over 140 academic papers and inventor of over 30 patents. Her research areas include phase transitions in computer science, structural and dynamical properties of networks, graph theory, graph algorithms, and computational biology. She is one of the inventors of the field of graphons, which are now widely used in the machine learning of massive networks. Chayes’ recent work focuses on machine learning, broadly defined. Chayes holds a BA in physics and biology from Wesleyan, where she graduated first in her class, and a PhD in physics from Princeton. She was a postdoctoral fellow at Harvard and Cornell. She is the recipient of the NSF Postdoc Fellowship, the Sloan Fellowship, the UCLA Distinguished Teaching Award, and the Anita Borg Institute Women of Leadership Vision Award. She has twice been a member of the Institute for Advanced Study in Princeton. Chayes is Fellow of the American Association for the Advancement of Science, the Fields Institute, the Association for Computing Machinery, and the American Mathematical Society, and the American Academy of Arts and Sciences. She is the winner of the 2015 John von Neumann Lecture Award, the highest honor of the Society of Industrial and Applied Mathematics. In 2016, she received an Honorary Doctorate from Leiden University. Chayes serves on numerous scientific boards and committees. She is a past VP of the American Mathematical Society, past Chair of Mathematics for the Association for the Advancement of Science, and past Chair of the Turing Award Selection Committee. She is also committed to diversity in the science and technology, and serves on many boards to increase representation of women and minorities in STEM.
More from the Same Authors
2019 Workshop: Tackling Climate Change with ML »
David Rolnick · Priya Donti · Lynn Kaack · Alexandre Lacoste · Tegan Maharaj · Andrew Ng · John Platt · Jennifer Chayes · Yoshua Bengio
2017 Poster: Thy Friend is My Friend: Iterative Collaborative Filtering for Sparse Matrix Estimation »
Christian Borgs · Jennifer Chayes · Christina Lee · Devavrat Shah
2015 Poster: Private Graphon Estimation for Sparse Graphs »
Christian Borgs · Jennifer Chayes · Adam Smith