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

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

基本信息

批准号：
1563838
负责人：
Santosh Vempala
金额：
$ 80万
依托单位：
Georgia Tech Research Corporation
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2016
资助国家：
美国
起止时间：
2016-09-01 至 2021-08-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1563838&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）对经典计数问题更快的随机算法。