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 将探索这种联系在其他设置中是否成立，例如，经过充分研究的 Ising 模型。本研究的另一个主题是马尔可夫链蒙特卡罗 (MCMC) 方法的改进技术，该方法通常用于随机抽样的算法中并近似计算大组组合对象的大小。 这项研究在依赖 MCMC 算法的各个领域都有应用，包括统计物理学和进化生物学中系统发育的贝叶斯推断。