Spring 2006 Seminar Series

DATE: Thursday, April 20, 2006
LOCATION: E40-298
TIME: 4:15pm
Reception immediately following in the Philip M. Morse Reading Room, E40-106

SPEAKER:
David Gamarnik

Assistant Professor of Operations Research

MIT

TITLE
Correlation Decay, Statistical Physics and Algorithmic Applications

ABSTRACT
It is well known that if a Markov chain is aperiodic then its temporal observations are asymptotically uncorrelated. It turns out that similar decay of correlation property occurs in many combinatorial structures, although the origin of this notion is statistical physics literature in 60's. In this talk we pursue a two-fold goal:

 

a) explore the structural properties of correlation decay and

b) exploit it for algorithms.

 

We will illustrate this on several applications:

 

1) The feasibility of a randomly generated sparse linear programming problem (random k-LSAT) exhibits an interesting phase transition behavior, similar to the conjectured behavior of a random k-SAT problem.

2) We construct polynomial time algorithms for several approximate counting problems. The algorithms work in the regime which is not currently captured by the most powerful approximate counting tool – rapidly mixing Markov chain.

 

Joint work with Antar Bandyopadhyay, Thomas Nowicki and Grzegorz Swirszcz