CAREER: Markov Chain Algorithms for Combinatorial Problems from Statistical Physics

这项研究致力于探索马尔可夫链的用途，重点是在统计物理和计算机科学中的应用。马尔科夫链在这些学科中被用来研究组合集合的特征，方法是允许(1)采样配置和(2)估计集合的基数。在统计物理学中，这样的集合作为简单物理系统的模型出现，其中的构型通常代表系统中分子的排列。采样提供了对系统热力学性质的洞察，例如比热和自由能。最近，在计算机科学中，已经开发了几种新的技术来证明某些类型的马尔可夫链正在快速混合。事实上，针对物理模型产生的问题的精确类型的算法已经取得了相当大的成功。这一项目代表了三种继续这项研究的新方式，这些方向将对两个领域都有利。(1)开发其他组合问题的可证明有效算法。两个有趣的问题是：(A)k-着色，它出现在Potts反铁磁性模型和冰模型中，以及(B)晶格区和超立方体上的哈密顿环，它在密码学(用于加密图像和生成随机格雷码)和生物物理学(用于研究聚合物的紧密构象)中有应用。(2)设计有限格子区域的采样算法，以深入了解无限格子上的相应问题(即连续统极限)。(3)发展马尔可夫链混合速率的分解技术，并利用“模拟回火”研究其应用。最后，这种跨学科研究将通过设计新的课程来补充，这些课程侧重于最近的研究成果(并鼓励与之相关的项目)，还将通过组织讲习班和研讨会，使相关学科的科学家汇聚一堂。

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.