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

AF：中：协作研究：近似计数的随机性的力量

• 批准号: 1563757
• 负责人: Daniel Stefankovic
• 金额: $ 40万
• 依托单位: University of Rochester
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-09-01 至 2021-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1563757&HistoricalAwards=false
• 关键词: AF; Medium; Collaborative; Research; Power

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.

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