Abstract: Loosely speaking, a complex system exhibits a correlation decay property if correlations between components of the system decay as a function of a distance between the components. The notion appears primarily in the context of Gibbs measures in statistical physics, but appears to have interesting algorithmic applications.

We first illustrate how the correlation decay property can be used to design a deterministic algorithm for counting partial matching of a graph. The running time of the algorithm is polynomial when the degree of the graph is constant and sub-exponential in the general case. Previous algorithm for this problem relied on Monte-Carlo technique and thus required randomization.

Then we discuss application of this method to the problem of computing the entropy (the limit of the log-partition function) of the monomer-dimer coverings of a lattice, improving significantly previous bounds.

Finally (time-permitting), we will discuss a problem of optimization on a graph where the costs associated with nodes edges are random. We show again that under certain assumption on the distribution of the cost, the system exhibits decay of correlation which leads to designing an efficient algorithm for deriving the optimal solution in polynomial time.

Joint work with Bayati, Katz, Nair, Tetali, Weber.