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

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

基本信息

  • 批准号:
    1563757
  • 负责人:
  • 金额:
    $ 40万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Continuing Grant
  • 财政年份:
    2016
  • 资助国家:
    美国
  • 起止时间:
    2016-09-01 至 2021-08-31
  • 项目状态:
    已结题

项目摘要

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)更快的随机算法对于经典的计数问题。

项目成果

期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

Daniel Stefankovic其他文献

Slice Normalized Dynamic Markov Logic Networks
切片归一化动态马尔可夫逻辑网络
  • DOI:
  • 发表时间:
    2012-12-03
  • 期刊:
  • 影响因子:
    0
  • 作者:
    T. Papai;Henry A. Kautz;Daniel Stefankovic
  • 通讯作者:
    Daniel Stefankovic
Fast Convergence of Markov Chain Monte Carlo Algorithms for Phylogenetic Reconstruction with Homogeneous Data on Closely Related Species
马尔可夫链蒙特卡罗算法的快速收敛,用于密切相关物种同质数据的系统发育重建
  • DOI:
    10.1137/100790550
  • 发表时间:
    2011-07-28
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Daniel Stefankovic;Eric Vigoda
  • 通讯作者:
    Eric Vigoda
Hanani-Tutte and Monotone Drawings
Hanani-Tutte 和单调图画
  • DOI:
    10.1007/978-3-642-25870-1_26
  • 发表时间:
    2011-06-21
  • 期刊:
  • 影响因子:
    0
  • 作者:
    R. Fulek;M. Pelsmajer;M. Schaefer;Daniel Stefankovic
  • 通讯作者:
    Daniel Stefankovic
Crossing Numbers and Parameterized Complexity
交叉数字和参数化复杂性
Set Systems with Restricted Intersections modulo Prime Powers
以素数幂为模的具有限制交点的集合系统
  • DOI:
    10.1006/jcta.2000.3149
  • 发表时间:
    2001-07-13
  • 期刊:
  • 影响因子:
    0
  • 作者:
    L. Babai;P. Frankl;S. Kutin;Daniel Stefankovic
  • 通讯作者:
    Daniel Stefankovic

Daniel Stefankovic的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Daniel Stefankovic', 18)}}的其他基金

Collaborative Research: AF: Small: Phase Transitions in Sampling Related Problems
合作研究:AF:小:采样相关问题中的相变
  • 批准号:
    2007287
  • 财政年份:
    2020
  • 资助金额:
    $ 40万
  • 项目类别:
    Standard Grant
AF: Small: Identifying sampling problems with efficient algorithms
AF:小:用高效算法识别采样问题
  • 批准号:
    1318374
  • 财政年份:
    2013
  • 资助金额:
    $ 40万
  • 项目类别:
    Standard Grant
AF: Large: Collaborative Research: Random Processes and Randomized Algorithms
AF:大型:协作研究:随机过程和随机算法
  • 批准号:
    0910415
  • 财政年份:
    2009
  • 资助金额:
    $ 40万
  • 项目类别:
    Standard Grant

相似国自然基金

基于机器学习和经典电动力学研究中等尺寸金属纳米粒子的量子表面等离激元
  • 批准号:
    22373002
  • 批准年份:
    2023
  • 资助金额:
    50 万元
  • 项目类别:
    面上项目
基于挥发性分布和氧化校正的大气半/中等挥发性有机物来源解析方法构建
  • 批准号:
    42377095
  • 批准年份:
    2023
  • 资助金额:
    49 万元
  • 项目类别:
    面上项目
中等质量黑洞附近的暗物质分布及其IMRI系统引力波回波探测
  • 批准号:
    12365008
  • 批准年份:
    2023
  • 资助金额:
    32 万元
  • 项目类别:
    地区科学基金项目
复合低维拓扑材料中等离激元增强光学响应的研究
  • 批准号:
    12374288
  • 批准年份:
    2023
  • 资助金额:
    52 万元
  • 项目类别:
    面上项目
中等垂直风切变下非对称型热带气旋快速增强的物理机制研究
  • 批准号:
    42305004
  • 批准年份:
    2023
  • 资助金额:
    30 万元
  • 项目类别:
    青年科学基金项目

相似海外基金

Collaborative Research: AF: Medium: Fast Combinatorial Algorithms for (Dynamic) Matchings and Shortest Paths
合作研究:AF:中:(动态)匹配和最短路径的快速组合算法
  • 批准号:
    2402284
  • 财政年份:
    2024
  • 资助金额:
    $ 40万
  • 项目类别:
    Continuing Grant
Collaborative Research: AF: Medium: The Communication Cost of Distributed Computation
合作研究:AF:媒介:分布式计算的通信成本
  • 批准号:
    2402835
  • 财政年份:
    2024
  • 资助金额:
    $ 40万
  • 项目类别:
    Continuing Grant
Collaborative Research: AF: Medium: The Communication Cost of Distributed Computation
合作研究:AF:媒介:分布式计算的通信成本
  • 批准号:
    2402836
  • 财政年份:
    2024
  • 资助金额:
    $ 40万
  • 项目类别:
    Continuing Grant
Collaborative Research: AF: Medium: Algorithms Meet Machine Learning: Mitigating Uncertainty in Optimization
协作研究:AF:媒介:算法遇见机器学习:减轻优化中的不确定性
  • 批准号:
    2422926
  • 财政年份:
    2024
  • 资助金额:
    $ 40万
  • 项目类别:
    Continuing Grant
Collaborative Research: AF: Medium: Adventures in Flatland: Algorithms for Modern Memories
合作研究:AF:媒介:平地历险记:现代记忆算法
  • 批准号:
    2423105
  • 财政年份:
    2024
  • 资助金额:
    $ 40万
  • 项目类别:
    Continuing Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了