CAREER: Markov Chain Algorithms for Combinatorial Problems from Statistical Physics

点击翻译按钮获取中文摘要

This research endeavors to explore uses of Markov chains, focusing on applications in statistical physics and computer science. Markov chains are used in these disciplines to study features of a combinatorial set by allowing (1) the sampling of configurations and (2) estimating the set's cardinality. In statistical physics such sets arise as models of simple physical systems, where the configurations typically represent arrangements of molecules in the system. Sampling provides insight into the thermodynamic properties of the system, such as the specific heat and free energy. Recently in computer science, several new techniques have been developed for proving that certain classes of Markov chains are rapidly mixing. In fact, there has been considerable success with algorithms for precisely the types of problems arising from physical models. This project represents three new ways of continuing this research in directions which will be beneficial to both fields. (1) Develop provably efficient algorithms for other combinatorial problems. Two problems of interest are: (a) k-coloring, which arises in the Potts model for antiferromagnetism, and the Ice model, and (b) Hamiltonian cycles on lattice regions and hypercubes, which has applications in cryptography (for encrypting images and generating random Gray code) and biophysics (for studying compact conformations of polymers). (2) Design sampling algorithms for finite lattice regions which will give insight into the corresponding problems in infinite lattices (i.e., the continuum limit). (3) Develop decomposition techniques for bounding the mixing rate of Markov chains and study applications using "`simulated tempering." Finally, this interdisciplinary research will be complemented by the design of new courses which focus on (and encourage projects related to) recent research results and through the organization of workshops and seminars which bring together scientists from the relevant disciplines.