AF: Small: Markov Chains, Statistical Physics, and Mobile Geometric Graphs

University Of California-Berkeley, Berkeley CA

Investigators

Abstract

The project has three main themes: 1. Markov chain Monte Carlo algorithms: The study of techniques such as lifting to speed up algorithms based on Markov chains, as well as the analysis of Markov chains---for lattice triangulations and the random cluster model---that are beyond the range of current techniques. 2. Statistical physics and computation: A continuing study of the Glauber dynamics for spin systems, focusing especially on the key open question of the influence of boundary conditions on the mixing time; the harnessing of an emerging understanding of spatial mixing to derive new algorithms and complexity results for counting and sampling problems; the application of new techniques for the analysis of the Boltzmann equation in physics to a computational study of nonlinear models in population genetics and genetic algorithms. 3. Mobile geometric graphs: A mathematically rigorous investigation of the effects -- in terms of both increased power and novel algorithmic challenges -- of introducing mobile nodes into models of wireless networks. Numerous connections among the themes provide intellectual coherence. For example, Markov chains play a central role in statistical physics through the Glauber dynamics; phase transitions and threshold phenomena appear in all three themes, as does the pervasive notion of dynamical evolution of a system over time; and the understanding of mobile geometric graphs is intimately connected with continuum percolation in physics. In addition, all three themes are examples of outreach from theoretical computer science to other disciplines, notably probability theory, statistical physics and wireless networking, and the project is expected to contribute to cross-fertilization between computer science and these fields. Throughout the project, the choice of research questions is driven not only by their intrinsic significance but also by the challenges that they present to existing techniques and the extent to which they illuminate connections with these other fields.