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.