Duke Computer Science Colloquium

Belief Propagation Algorithms: From Matching Problems to Network Discovery in Cancer Genomics

Speaker:Jennifer Chayes
Date: Thursday, March 31, 2016
Time: 1:00pm - 2:00pm
Location: D106 LSRC, Duke


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 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. Before joining Microsoft in 1997, Chayes was for many years Professor of Mathematics at UCLA. Chayes is the author of over 130 academic papers and the inventor of over 30 patents. Her research areas include phase transitions in discrete mathematics and computer science, structural and dynamical properties of self-engineered networks, graph algorithms and algorithmic game theory. Chayes is one of the inventors of the theory of graph limits, which is widely used for machine learning of massive networks. 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. Chayes has been the recipient of many leadership awards including the Leadership Award of Women Entrepreneurs in Science and Technology, the Women Who Lead Award, 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, the Association for Computing Machinery, and the American Mathematical Society, and an Elected Member of the American Academy of Arts and Sciences. Chayes is the recipient of the 2015 John von Neumann Lecture Award, the highest honor of the Society for Industrial and Applied Mathematics. She has been awarded an Honorary Doctorate from Leiden University.

Hosted by:
Debmalya Panigrahi