CAREER: Markov Chain Algorithms for Combinatorial Problems from Statistical Physics

本研究致力于探索马尔可夫链的应用，重点是在统计物理和计算机科学中的应用。 马尔可夫链在这些学科中用于研究组合集的特征，允许（1）配置的采样和（2）估计集合的基数。 在统计物理学中，这样的集合作为简单物理系统的模型出现，其中配置通常代表系统中分子的排列。 采样提供了对系统热力学性质的深入了解，例如比热和自由能。 最近在计算机科学中，已经开发了几种新的技术来证明某些类别的马尔可夫链是快速混合的。 事实上，对于由物理模型产生的精确问题类型的算法已经取得了相当大的成功。 该项目代表了三种新的方式继续这一研究的方向，这将有利于这两个领域。 (1)为其他组合问题开发可证明有效的算法。 两个令人感兴趣的问题是：（a）k-着色，它出现在Potts反铁磁性模型和Ice模型中，（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.