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 中心联合举办。 明年，该计划将以与这一跨学科研究领域出现的科学主题相关的额外研讨会和工作组结束。