Markov Chain Algorithms for Problems from Computer Science and Statistical Physics

用于计算机科学和统计物理问题的马尔可夫链算法

• 批准号: 0830367
• 负责人: Dana Randall
• 金额: $ 30万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-08-01 至 2012-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0830367&HistoricalAwards=false
• 关键词: Markov; Chain; Algorithms; Problems; Computer

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.

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