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模型。这项研究中的另一个主要主题是改进的Markov Chain Chain Monte Carlo（MCMC）方法的技术，这些技术通常用于算法中，用于从算法中进行随机采样，并大致计算结合物体的大型组合大小。 这项研究在依赖MCMC算法的各个领域中有应用，包括统计物理学和贝叶斯在进化生物学中的系统发育。