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

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

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.