AF: Medium: Collaborative Research: The Power of Randomness for Approximate Counting

在理论计算机科学中，对计数问题复杂性的研究有着悠久而丰富的历史。计数问题（以及密切相关的抽样问题）在许多不同的领域自然出现，例如，在统计物理学中，它们对应于配分函数，用于研究物理系统理想化模型的平衡状态，在贝叶斯推理中，它们用于研究后验分布或最大似然分布。这里讨论的具体问题是长期悬而未决的问题，在这些问题上的进展将引起广泛的兴趣。该项目将开发用于近似计数的新工具，并可能在统计物理、概率和计算复杂性之间建立新的有用的联系。研究结果将通过课程笔记、暑期学校和讲习班传播。得出的任何实用算法都将向公众开放。该项目的总体目标是扩展计数问题的多项式时间可追溯性的已知边界，了解随机性是否必要以及如何消除随机性，并将当前最快的随机算法的极限推向实用性。具体目标包括：(1)多项式时间随机逼近方案，用于解决一些迄今为止无法有效解决的基本问题；(2)确定性多项式时间近似方案，用于解决一些著名的随机算法的中心问题；(3)经典计数问题的更快随机算法。

The study of the complexity of counting problems has a long and rich history in theoretical computer science. Counting problems (and closely related sampling problems) arise naturally in many different fields, for example in statistical physics they correspond to partition functions and for studies of the equilibrium states of idealized models of physical systems, and in Bayesian inference they arise for the study of posterior distributions or maximum likelihood distributions. The specific questions addressed here are long-standing open problems, progress on which will be of wide interest. The project will develop new tools for approximate counting and is likely to make new and useful connections between statistical physics, probability and computational complexity. The research results will be disseminated via course notes, a summer school and workshops. Any practical algorithms that result will be made publicly available.The overall goal of the project is to extend the known boundary of polynomial-time tractability for counting problems, to understand whether randomness is essential and how it could be eliminated, and to push the limits of the current fastest randomized algorithms towards practicality. Specific aims include: (1) Polynomial-time randomized approximation schemes for some fundamental problems that have thus far eluded efficient solutions, (2) Deterministic polynomial-time approximation schemes for some central problems that have celebrated randomized algorithms and (3) Faster randomized algorithms for classical counting problems.