Markov Chain Algorithms for Problems from Computer Science and Statistical Physics

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

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

This proposal focuses on the connections between the efficiency of algorithms and phase transitions in related physical systems. Arguments for showing slow mixing, or the inefficiency, of Markov chains and the presence of phase transitions typically rely on sophisticated counting arguments. A new approach based on topological obstructions is suggested that would greatly simplify these arguments and moreover would strengthen known results. This will be explored in the context of independent sets and colorings in fixed dimensional lattices. A related topic examined in this proposal concerns the effects of boundary conditions on the mixing rates of certain Markov chains. Boundary conditions play a crucial role in the study of phase transitions of statistical physics models on the infinite lattice, so understanding their influence on the mixing rate of finite chains could provide insights for both the design of algorithms and the behavior of the underlying systems.Over the last ten years, a new interdisciplinary field has emerged at the interface of discrete probability, computer science and statistical physics. The research component of this proposal explores new directions for enhancing the connections between these fields in order to design better algorithms and study phase transitions of physical systems. Many of the questions posed, and the technical tools suggested for their solutions, are the result of a bilateral interplay between fields. This research will be supplemented through an educational component. Starting in Fall 2006, the P.I. will be chairing the organizing committee of a DIMACS/Georgia Tech special focus on "Discrete Random Systems," concentrating on this area of interdisciplinary research. In addition to the typical workshops bringing together leading researchers in the relevant areas, there will also be workshops and working groups promoting broader impact, both in terms of participants and topics. Tutorials will be included when beneficial.

该提案重点关注算法效率与相关物理系统中的相变之间的联系。 证明马尔可夫链混合缓慢或效率低下以及存在相变的论据通常依赖于复杂的计数论据。 一个新的方法的基础上拓扑障碍的建议，将大大简化这些参数，而且会加强已知的结果。这将在固定维格中的独立集和着色的上下文中进行探索。 在这个建议中研究的一个相关主题涉及边界条件对某些马尔可夫链的混合率的影响。 边界条件在无限格点上统计物理模型的相变研究中起着至关重要的作用，因此了解边界条件对有限链混合速率的影响可以为算法设计和底层系统的行为提供见解。近十年来，在离散概率、计算机科学和统计物理的交界处出现了一个新的交叉学科领域。 该提案的研究部分探索了加强这些领域之间联系的新方向，以设计更好的算法并研究物理系统的相变。 所提出的许多问题以及为解决这些问题而建议的技术工具，都是各领域之间双边相互作用的结果。 这项研究将通过教育部分得到补充。 从2006年秋季开始，P.I.将主持一个DIMACS/格鲁吉亚技术特别关注“离散随机系统”的组织委员会，专注于跨学科研究的这一领域。 除了将相关领域的主要研究人员聚集在一起的典型讲习班外，还将举办讲习班和工作组，促进在参与者和主题方面产生更广泛的影响。 如果受益，将包括学费。