Rajesh Sundaresan, Indian Institute of Science
Abstract: The tutorial will provide an overview of the belief propagation (BP) algorithm and its usefulness in addressing random instances of combinatorial optimization problems (matching, edge-cover, the traveling salesman problem, load-balancing, etc.) on locally tree-like graphs. The tutorial will cover the following topics: description of iterative BP algorithms for finding marginals, max-marginals, etc. on a graphical model, issues related to convergence and correctness of the iterations, mapping of random instances of optimization problems as ground states of associated disordered statistical physics systems, cavity equations, their solutions, properties of the ground states, and approaches to establish correctness in locally tree-like settings.
Bio: Rajesh Sundaresan is a Professor in the Department of Electrical Communication Engineering and an Associate Faculty in the Robert Bosch Centre for Cyber-Physical Systems at the Indian Institute of Science. His interests are in communication, computation, and control over networks. He was an associate editor of the IEEE Transactions on Information Theory for the period 2012-2015. He received the B.Tech. degree in electronics and communication from the Indian Institute of Technology Madras, the M.A. and Ph.D. degrees in electrical engineering from Princeton University in 1996 and 1999, respectively. From 1999 to 2005, he worked at Qualcomm Inc. on the design of communication algorithms for wireless modems. Since 2005, he has been with the Indian Institute of Science with brief visiting positions at Qualcomm (2007), Coordinated Sciences Laboratory of the University of Illinois at Urbana-Champaign (2012-13), and the Toulouse Mathematics Institute (2015).