AF: Small: Approximate Counting, Markov Chains and Phase Transitions

AF：小：近似计数、马尔可夫链和相变

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

This project studies algorithms for counting and sampling problems. For an exponentially large set of discrete, combinatorial objects, the goal is to estimate the size of this set or randomly sample from it in polynomial-time. Algorithms for these problems are used in a variety of scientific fields, often with little rigorous guarantees on their performance, and the results of this project will enhance the reliability of such studies. The results of this project will enhance connections between statistical physics and theoretical computer science by formalizing connections between phase transitions in statistical physics with the efficiency of algorithms for this type of counting/sampling problems. In addition, the PI will organize inter-disciplinary workshops tying together researchers from statistical physics, discrete mathematics, and theoretical computer science.Loopy Belief Propagation (BP) and Markov Chain Monte Carlo (MCMC) algorithms are two popular algorithms for the counting/sampling problems of approximating partition functions and sampling from Gibbs distributions. In this project the PI intends to present new techniques for proving convergence results for loopy BP and MCMC algorithms. This will result in new, efficient counting/sampling algorithms for problems of combinatorial interest including weighted independent sets and colorings of a graph. These results will enhance recent results establishing beautiful connections between the approximability of counting problems for graphs of maximum degree D with statistical physics phase transitions for infinite D-regular trees.

该项目研究计数和采样问题的算法。 对于指数级大的离散组合对象集，目标是估计该集的大小或在多项式时间内从中随机采样。这些问题的算法被用于各种科学领域，通常对其性能几乎没有严格的保证，该项目的结果将提高此类研究的可靠性。 该项目的结果将通过形式化统计物理学中的相变与此类计数/采样问题的算法效率之间的联系来增强统计物理学和理论计算机科学之间的联系。此外，PI 将组织跨学科研讨会，将统计物理学、离散数学和理论计算机科学的研究人员聚集在一起。循环置信传播 (BP) 和马尔可夫链蒙特卡罗 (MCMC) 算法是两种流行的计数/采样算法近似配分函数和吉布斯分布采样的问题。在这个项目中，PI 打算提出新技术来证明循环 BP 和 MCMC 算法的收敛结果。这将为组合感兴趣的问题（包括加权独立集和图的着色）带来新的、高效的计数/采样算法。这些结果将增强最近的结果，在最大 D 度图的计数问题的近似性与无限 D 正则树的统计物理相变之间建立良好的联系。