Approximate Counting, Statistical Physics and Computation

University Of California-Berkeley, Berkeley CA

Investigators

Abstract

Abstract The project contains two main themes that are related in various ways: (1) approximation algorithms for counting problems, and (2) computational aspects of statistical physics. Counting problems arise in numerous application areas, including combinatorics, algebra, volume and integration, statistical physics, computational finance and statistical hypothesis testing. In almost all cases they are intractable in exact form; theme (1) of the project is focused on constructing efficient algorithms for these problems that guarantee any desired degree of approximation. Theme (2) of the project aims to better understand deep emerging connections between phase transitions in physical systems on the one hand, and computational complexity or the running time of algorithms on the other. The two themes are united by various algorithmic and mathematical techniques (notably, the Markov chain Monte Carlo paradigm). In addition, there is a focus in the project on the application of ideas from theoretical Computer Science to problems in other sciences. Specific goals of theme (1) include the following: to resolve the status of a number of important counting problems, either by developing efficient approximation algorithms or by proving them hard to approximate; to construct more efficient approximation algorithms for central problems in the field; and to explore novel application areas such as computational finance. Specific topics to be addressed within theme (2) include the mixing time of Glauber dynamics; the behavior of message-passing algorithms such as Belief Propagation; and connections between physical models and random constraint satisfaction problems.