Colloquium Details
Message Passing Networks
Speaker: Devavrat Shah, Massachusetts Institute of Technology
Location: Warren Weaver Hall 1302
Date: March 12, 2010, 11:30 a.m.
Host: Lakshmi Subramanian
Synopsis:
Simple, distributed and iterative algorithms, popularly known as message-passing, have emerged as the architecture of choice for a variety of networks. They have been surprisingly effective despite their simplicity. In this talk, I will try to argue in favor of such algorithms by discussing examples from communication networks and statistical inference.
In the first part, I will discuss the design of an efficient medium access algorithm for wireless networks. Here nodes wish to transmit without interfering with each other while maximizing utilization of the wireless medium. To minimize co-ordination cost, solutions implemented in practice are based on `random access'. However, they perform quite poorly as proved in theory and observed in practice. I will present an `adaptive' random access algorithm that is provably efficient. This work draws insights from the classical variational principle, mixing times of Markov chains and reversibility.
In the second part, I will discuss strengths and limitations of the popular message passing heuristic called belief propagation (BP) for inference in graphical models. BP arose as a distributed, dynamic programming based approximation for tree-like graphs. However, it seems to work quite well empirically even when graphical models are far from tree-like. I will attempt to explain this unexpected behavior by drawing connection between BP and Linear Programing for a class of optimization problems.
Speaker Bio:
Devavrat Shah is currently a Jamieson career development associate professor with the department of electrical engineering and computer science, MIT. He is a member of the Laboratory for Information and Decision Systems (LIDS). His research focus is on the theory of large complex networks which includes network algorithms, stochastic networks, network information theory and large scale statistical inference. He was co-awarded the best paper awards at the IEEE INFOCOM '04, ACM SIGMETRICS/Performance '06; and supervised work that received the best student paper awards at Neural Information Processing Systems'08 and ACM SIGMETRICS/Performance '09. He received the 2005 George B. Dantzig best dissertation award from the INFORMS. He received the first ACM SIGMETRICS Rising Star Award 2008 for his work on network scheduling algorithms. He is currently an associate editor of Operations Research.
Notes:
In-person attendance only available to those with active NYU ID cards.