Approximate Counting, Markov Chains and Phase Transitions

University Of California-Berkeley, Berkeley CA

Investigators

Abstract

Markov chains play an important role in a variety of fields, but the analysis of their convergence properties remains a challenging problem. The emphasis of this workshop is on the analysis of "large" Markov chains, i.e., finite-state chains where the number of states is exponentially large as a function of the description size of an individual state. Such chains are especially important in the study of statistical physics models and the design of approximate counting algorithms. The workshop will bring together researchers in the analysis of large Markov chains from many areas of application, to review progress and to identify challenges for future research. Recently there has been considerable success in designing approximate counting algorithms without the use of Markov chains, relying instead on so-called "spatial mixing" properties. Remarkably, matching hardness results have been established in the special case of antiferromagnetic 2-spin systems. This beautiful collection of results ties together the complexity of approximate counting on a general class of graphs with an associated phase transition for the infinite regular tree. By highlighting recent results in the study of approximate counting problems, the workshop will explore analogous connections for other models and for related problems. Video tapes of presentations and discussions will be distributed to the public. Students will be encouraged to participate in this interdisciplinary area.