AF: Small: Phase Transitions in Approximate Counting Problems

AF：小：近似计数问题中的相变

• 批准号: 1217458
• 负责人: Eric Vigoda
• 金额: $ 38.29万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-09-01 至 2016-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1217458&HistoricalAwards=false
• 关键词: AF; Small; Phase; Transitions; Approximate

This award explores connections between the computational complexity of approximate counting problems and phase transitions in Statistical Physics models. Recent work implies that the computational complexity of approximately counting weighted independent sets in general graphs undergoes a phase transition that coincides with a classical Statistical Physics phase transition on trees. PI will explore whether such connections hold in other settings, for example, the well-studied Ising model.Another main theme in this research are improved techniques for Markov Chain Monte Carlo (MCMC) methods, which are often used in algorithms for randomly sampling from and approximately counting the size of large sets of combinatorial objects. This research has applications in a variety of fields which rely on MCMC algorithms, including Statistical Physics and Bayesian inference of phylogeny in Evolutionary Biology.

该奖项探讨了统计物理模型中近似计数问题的计算复杂性与相变之间的联系。最近的研究表明，一般图中近似计数加权独立集的计算复杂性经历了与树的经典统计物理相变相一致的相变。PI将探索这种联系是否在其他情况下也成立，例如，已经得到充分研究的伊辛模型。本研究的另一个主题是马尔可夫链蒙特卡罗（MCMC）方法的改进技术，该方法通常用于从大型组合对象集合中随机抽样和近似计数大小的算法。这项研究在许多依赖MCMC算法的领域都有应用，包括统计物理学和进化生物学中系统发育的贝叶斯推断。