AF: Small: Phase Transitions in Approximate Counting Problems

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

This award explores connections between the computational complexity of approximate counting problems and phase transitions in Statistical Physics models. Recent work implies that the computational complexity of approximately counting weighted independent sets in general graphs undergoes a phase transition that coincides with a classical Statistical Physics phase transition on trees. PI will explore whether such connections hold in other settings, for example, the well-studied Ising model. Another main theme in this research are improved techniques for Markov Chain Monte Carlo (MCMC) methods, which are often used in algorithms for randomly sampling from and approximately counting the size of large sets of combinatorial objects. This research has applications in a variety of fields which rely on MCMC algorithms, including Statistical Physics and Bayesian inference of phylogeny in Evolutionary Biology.