Markov Chain Algorithms for Problems from Computer Science and Statistical Physics

马尔可夫链蒙特卡罗算法有着惊人的应用范围，包括近似计数，组合优化和建模。 确定马尔可夫链的混合时间通常是证明这些基于随机抽样的近似算法的有效性的重要步骤。该项目的主要目标包括：识别适合这种方法的问题，为这些问题设计可证明有效的算法，并为严格的分析开发概率参数。 对于这些目标中的每一个，理论计算机科学都从与其他学科的相互作用中受益匪浅，特别是统计物理学。在这个项目中，研究人员探索计算和物理交叉点的问题。 该项目的前半部分研究了纳米技术，细胞自动机和视觉中出现的计算问题，其中提出的解决方案是基于马尔可夫链蒙特卡罗方法。 该研究考察了这些方法是否是好的解决方案，并提出了更有效的替代方案。 该项目的第二部分探索了计算机科学和物理学之间的一些基本联系，包括底层物理模型中的相变与某些局部采样算法的缓慢混合（或低效率）之间的关系。 此外，这项研究将得到一个正在进行的离散随机系统计划的补充，该计划由研究人员共同组织，并在格鲁吉亚理工学院和罗格斯大学的DIMACS中心联合举行。 在接下来的一年里，该计划将结束与从这个跨学科研究领域出现的科学主题相关的其他研讨会和工作组。

Markov chain Monte Carlo algorithms have an astounding variety of applications, including approximate counting, combinatorial optimization and modeling. Determining the mixing time of Markov chains is often the vital step in proving the efficiency of these approximation algorithms based on random sampling. The primary goals of this project include: identifying problems amenable to this approach, designing provably efficient algorithms for these problems, and developing probabilistic arguments for their rigorous analysis. For each of these goals, theoretical computer science has benefited greatly from interactions with other disciplines, most notably statistical physics. In this project, the investigator explores problems at the intersection of computation and physics. The first half of the project examines computational problems arising in nanotechnology, cellular-automata, and vision, where proposed solutions are based on Markov chain Monte Carlo methods. The research examines whether these heuristics are good solutions, and suggests more efficient alternatives. The second part of the project explores some fundamental connections between computer science and physics, including the relationship between phase transitions in the underlying physical models and slow mixing (or the inefficiency) of certain local sampling algorithms. In addition, this research will be supplemented by an ongoing program on Discrete Random Sysstems, co-organized by the investigator, and held jointly at Georgia Tech and the DIMACS Center at Rutgers University. Over the next year the program will conclude with additional workshops and working groups related to scientific themes emerging from this interdisciplinary research area.