AF: Small: Approximate Counting, Markov Chains and Phase Transitions

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

This project studies algorithms for counting and sampling problems. For an exponentially large set of discrete, combinatorial objects, the goal is to estimate the size of this set or randomly sample from it in polynomial-time. Algorithms for these problems are used in a variety of scientific fields, often with little rigorous guarantees on their performance, and the results of this project will enhance the reliability of such studies. The results of this project will enhance connections between statistical physics and theoretical computer science by formalizing connections between phase transitions in statistical physics with the efficiency of algorithms for this type of counting/sampling problems. In addition, the PI will organize inter-disciplinary workshops tying together researchers from statistical physics, discrete mathematics, and theoretical computer science. Loopy Belief Propagation (BP) and Markov Chain Monte Carlo (MCMC) algorithms are two popular algorithms for the counting/sampling problems of approximating partition functions and sampling from Gibbs distributions. In this project the PI intends to present new techniques for proving convergence results for loopy BP and MCMC algorithms. This will result in new, efficient counting/sampling algorithms for problems of combinatorial interest including weighted independent sets and colorings of a graph. These results will enhance recent results establishing beautiful connections between the approximability of counting problems for graphs of maximum degree D with statistical physics phase transitions for infinite D-regular trees.