Decision and Control Lecture Series

Decision and Control Laboratory, Coordinated Science Laboratory

Statistical physics methods for optimization and inference on networks

David Gamarnik

Nanyang Technological University Professor of Operations Research

Sloan School of Management

Massachusetts Institute of Technology

Wednesday, April 3, 2013

3:00 p.m. to 4:00 p.m.

B02 Auditorium CSL

___________________________________________________________________________________________________________________________________________________________________________________________

Abstract

Statistical physics focuses on microscopic properties of matter using probabilistic and graph theoretic models. However, some concepts in the field of statistical physics, such as the long range independence (correlation decay) property and phase transition property, have applications far beyond the original scope of physics. We illustrate applications of the correlation decay method in several areas of interest to optimization and machine learning communities, including combinatorial optimization on graphs, inference in graphical models (Markov Random Fields) and reconstruction of graphical models. For the illustration purposes, we will show how introducing random weights into a graph can turn a hard problem of finding a largest independent set of a graph into an approximately tractable problem, by means of inducing the correlation decay property. No knowledge of statistical physics is expected for the talk.

Biography

David Gamarnik is a Nanyang Technological University  Professor of Operations Research  at the Sloan School of Management of Massachusetts Institute of Technology. He received B.A. in mathematics from New York University in 1993 and Ph.D. in Operations Research from MIT in 1998. Since then he was a research staff member of IBM T.J. Watson Research Center, before joining MIT in 2005.

His research interests include applied probability and stochastic processes, theory of random graphs, algorithms and combinatorial optimization, and variety of applications.  He is a recipient of the Erlang Prize and the Best Publication Award from the INFORMS Applied Probability Society, IBM Faculty Partnership Award and several NSF sponsored grants. He is an area editor of Operations Research journal and associate editor of Mathematics of Operations Research, Stochastic Systems, and  Queueing Systems journals.

 PLEASE JOIN US FOR COOKIES AND COFFEE IMMEDIATELY FOLLOWING THE SEMINAR IN THE LOWER LEVEL LOBBY