Markov chain Monte Carlo algorithms have an astounding variety of applications, including approximate counting, combinatorial optimization and modeling. Determining the mixing time of Markov chains is often the vital step in proving the efficiency of these approximation algorithms based on random sampling. The primary goals of this project include: identifying problems amenable to this approach, designing provably efficient algorithms for these problems, and developing probabilistic arguments for their rigorous analysis. For each of these goals, theoretical computer science has benefited greatly from interactions with other disciplines, most notably statistical physics. In this project, the investigator explores problems at the intersection of computation and physics. The first half of the project examines computational problems arising in nanotechnology, cellular-automata, and vision, where proposed solutions are based on Markov chain Monte Carlo methods. The research examines whether these heuristics are good solutions, and suggests more efficient alternatives. The second part of the project explores some fundamental connections between computer science and physics, including the relationship between phase transitions in the underlying physical models and slow mixing (or the inefficiency) of certain local sampling algorithms. In addition, this research will be supplemented by an ongoing program on Discrete Random Sysstems, co-organized by the investigator, and held jointly at Georgia Tech and the DIMACS Center at Rutgers University. Over the next year the program will conclude with additional workshops and working groups related to scientific themes emerging from this interdisciplinary research area.
