This proposal focuses on the connections between the efficiency of algorithms and phase transitions in related physical systems. Arguments for showing slow mixing, or the inefficiency, of Markov chains and the presence of phase transitions typically rely on sophisticated counting arguments. A new approach based on topological obstructions is suggested that would greatly simplify these arguments and moreover would strengthen known results. This will be explored in the context of independent sets and colorings in fixed dimensional lattices. A related topic examined in this proposal concerns the effects of boundary conditions on the mixing rates of certain Markov chains. Boundary conditions play a crucial role in the study of phase transitions of statistical physics models on the infinite lattice, so understanding their influence on the mixing rate of finite chains could provide insights for both the design of algorithms and the behavior of the underlying systems.
Over the last ten years, a new interdisciplinary field has emerged at the interface of discrete probability, computer science and statistical physics. The research component of this proposal explores new directions for enhancing the connections between these fields in order to design better algorithms and study phase transitions of physical systems. Many of the questions posed, and the technical tools suggested for their solutions, are the result of a bilateral interplay between fields. This research will be supplemented through an educational component. Starting in Fall 2006, the P.I. will be chairing the organizing committee of a DIMACS/Georgia Tech special focus on "Discrete Random Systems," concentrating on this area of interdisciplinary research. In addition to the typical workshops bringing together leading researchers in the relevant areas, there will also be workshops and working groups promoting broader impact, both in terms of participants and topics. Tutorials will be included when beneficial.
