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还将组织跨学科研讨会，将统计物理、离散数学和理论计算机科学的研究人员联系在一起。Loopy Belief Propagation（BP）和Markov Chain Monte Carlo（MCMC）算法是两种流行的算法，用于近似分区函数和Gibbs分布采样的计数/采样问题。在这个项目中，PI打算提出新的技术来证明循环BP和MCMC算法的收敛结果。这将导致新的，有效的计数/采样算法的组合感兴趣的问题，包括加权独立集和着色的图形。这些结果将加强最近的结果之间建立美丽的连接的最大程度的D统计物理相变无限D-正则树图的计数问题的近似性。