Collaborative Research: AF: Small: Weak Derandomizations in Time and Space Complexity

合作研究:AF:小:时间和空间复杂性的弱去随机化

基本信息

  • 批准号:
    2130608
  • 负责人:
  • 金额:
    $ 27.2万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Standard Grant
  • 财政年份:
    2021
  • 资助国家:
    美国
  • 起止时间:
    2021-10-01 至 2024-09-30
  • 项目状态:
    已结题

项目摘要

Certain computational tasks such as network connectivity, sorting, and testing whether a number is a prime number admit time-efficient algorithms. On the other hand, many computational tasks, such as the traveling salesperson problem, integer factoring, and several other optimization problems, are not known to admit fast algorithms. Why does such computational disparity exist among natural computational tasks? This is a foundational question that impacts many scientific areas including mathematics, engineering, economics, optimization, and communication -- areas beyond computer science. Computational complexity theory investigates the notion of efficient computation. Typically, efficiency is measured in terms of computational resources such as time, memory, and randomness. This project aims to advance the state-of-the-art in computational complexity theory by investigating the role of randomness and its interplay with time and memory. Research findings from this project will be published in peer-reviewed venues as well as in open access venues enabling broad dissemination of scientific results. Efforts will be taken to integrate research with teaching at both graduate and undergraduate levels.Even though there is strong scientific evidence that randomized computations can be efficiently derandomized, establishing unconditional and complete derandomization results is known to be well beyond the current techniques in the field. In this context, this project will investigate certain weak but unconditional derandomizations. This is achieved by exploring (a) pseudodeterministic algorithms -- randomized algorithms that output a canonical value with high probability, and their relation to some central topics in complexity theory including completeness, promise problems, and circuit complexity; and (b) probabilistic space-bounded computations with multiple access to the random tape, and their relation to derandomization of time-bounded probabilistic classes.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.
某些计算任务,如网络连接,排序和测试一个数字是否是素数,允许时间有效的算法。另一方面,许多计算任务,如旅行推销员问题,整数因子分解,和其他几个优化问题,不知道承认快速算法。为什么在自然计算任务中存在这种计算差异?这是一个影响许多科学领域的基础问题,包括数学,工程,经济学,优化和通信-计算机科学以外的领域。计算复杂性理论研究有效计算的概念。通常,效率是根据计算资源(如时间、内存和随机性)来衡量的。该项目旨在通过研究随机性的作用及其与时间和记忆的相互作用来推进计算复杂性理论的最新发展。该项目的研究结果将在同行评审的场所以及开放获取的场所发表,以便广泛传播科学成果。尽管有强有力的科学证据表明,随机计算可以有效地去随机化,但建立无条件和完全的去随机化结果远远超出了该领域目前的技术。在这种情况下,本项目将研究某些弱但无条件的去随机化。这是通过探索(a)伪确定性算法--以高概率输出规范值的随机算法,以及它们与复杂性理论中的一些中心主题的关系,包括完备性、承诺问题和电路复杂性;以及(B)利用对随机带的多路访问的概率空间有界计算,该奖项反映了NSF的法定使命,并被认为值得通过使用基金会的知识价值和更广泛的影响审查标准进行评估来支持。

项目成果

期刊论文数量(6)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Pseudodeterminism: promises and lowerbounds
伪决定论:承诺和下限
  • DOI:
    10.1145/3519935.3520043
  • 发表时间:
    2022
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Dixon, Peter;Pavan, A.;Woude, Jason Vander;Vinodchandran, N. V.
  • 通讯作者:
    Vinodchandran, N. V.
Model Counting Meets Distinct Elements in a Data Stream
  • DOI:
    10.1145/3542700.3542721
  • 发表时间:
    2022-05
  • 期刊:
  • 影响因子:
    0
  • 作者:
    A. Pavan;N. V. Vinodchandran;Arnab Bhattacharyya;Kuldeep S. Meel
  • 通讯作者:
    A. Pavan;N. V. Vinodchandran;Arnab Bhattacharyya;Kuldeep S. Meel
Estimation of the Size of Union of Delphic Sets: Achieving Independence from Stream Size
Delphic 集并集大小的估计:实现与流大小的独立性
On Approximating Total Variation Distance
  • DOI:
    10.24963/ijcai.2023/387
  • 发表时间:
    2022-06
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Arnab Bhattacharyya;Sutanu Gayen;Kuldeep S. Meel;Dimitrios Myrisiotis;A. Pavan;N. V. Vinodchandran
  • 通讯作者:
    Arnab Bhattacharyya;Sutanu Gayen;Kuldeep S. Meel;Dimitrios Myrisiotis;A. Pavan;N. V. Vinodchandran
Distinct Elements in Streams: An Algorithm for the (Text) Book
流中的不同元素:(文本)书籍的算法
{{ 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 }}

Vinodchandran Variyam其他文献

Vinodchandran Variyam的其他文献

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

{{ truncateString('Vinodchandran Variyam', 18)}}的其他基金

Collaborative Research: AF: Small: New Directions in Algorithmic Replicability
合作研究:AF:小:算法可复制性的新方向
  • 批准号:
    2342244
  • 财政年份:
    2024
  • 资助金额:
    $ 27.2万
  • 项目类别:
    Standard Grant
EAGER: AF: Collaborative Research: Weak Derandomizations in Time and Space Complexity
EAGER:AF:协作研究:时间和空间复杂性中的弱去随机化
  • 批准号:
    1849048
  • 财政年份:
    2018
  • 资助金额:
    $ 27.2万
  • 项目类别:
    Standard Grant
AF: Small: Collaborative Research:Exploring New Approaches in Space Bounded Computation
AF:小型:协作研究:探索空间有限计算的新方法
  • 批准号:
    1422668
  • 财政年份:
    2014
  • 资助金额:
    $ 27.2万
  • 项目类别:
    Standard Grant
AF: Small: Collaborative Research: Studies in Nonuniformity, Completeness, and Reachability
AF:小型:协作研究:非均匀性、完整性和可达性的研究
  • 批准号:
    0916525
  • 财政年份:
    2009
  • 资助金额:
    $ 27.2万
  • 项目类别:
    Standard Grant
Collaborative Research: Research in Computational Complexity
合作研究:计算复杂性研究
  • 批准号:
    0830730
  • 财政年份:
    2008
  • 资助金额:
    $ 27.2万
  • 项目类别:
    Standard Grant
Studies in Computational Complexity Theory
计算复杂性理论研究
  • 批准号:
    0430991
  • 财政年份:
    2004
  • 资助金额:
    $ 27.2万
  • 项目类别:
    Standard Grant

相似国自然基金

Research on Quantum Field Theory without a Lagrangian Description
  • 批准号:
    24ZR1403900
  • 批准年份:
    2024
  • 资助金额:
    0.0 万元
  • 项目类别:
    省市级项目
Cell Research
  • 批准号:
    31224802
  • 批准年份:
    2012
  • 资助金额:
    24.0 万元
  • 项目类别:
    专项基金项目
Cell Research
  • 批准号:
    31024804
  • 批准年份:
    2010
  • 资助金额:
    24.0 万元
  • 项目类别:
    专项基金项目
Cell Research (细胞研究)
  • 批准号:
    30824808
  • 批准年份:
    2008
  • 资助金额:
    24.0 万元
  • 项目类别:
    专项基金项目
Research on the Rapid Growth Mechanism of KDP Crystal
  • 批准号:
    10774081
  • 批准年份:
    2007
  • 资助金额:
    45.0 万元
  • 项目类别:
    面上项目

相似海外基金

Collaborative Research: AF: Medium: The Communication Cost of Distributed Computation
合作研究:AF:媒介:分布式计算的通信成本
  • 批准号:
    2402836
  • 财政年份:
    2024
  • 资助金额:
    $ 27.2万
  • 项目类别:
    Continuing Grant
Collaborative Research: AF: Medium: Foundations of Oblivious Reconfigurable Networks
合作研究:AF:媒介:遗忘可重构网络的基础
  • 批准号:
    2402851
  • 财政年份:
    2024
  • 资助金额:
    $ 27.2万
  • 项目类别:
    Continuing Grant
Collaborative Research: AF: Small: New Directions in Algorithmic Replicability
合作研究:AF:小:算法可复制性的新方向
  • 批准号:
    2342244
  • 财政年份:
    2024
  • 资助金额:
    $ 27.2万
  • 项目类别:
    Standard Grant
Collaborative Research: AF: Small: Exploring the Frontiers of Adversarial Robustness
合作研究:AF:小型:探索对抗鲁棒性的前沿
  • 批准号:
    2335411
  • 财政年份:
    2024
  • 资助金额:
    $ 27.2万
  • 项目类别:
    Standard Grant
NSF-BSF: Collaborative Research: AF: Small: Algorithmic Performance through History Independence
NSF-BSF:协作研究:AF:小型:通过历史独立性实现算法性能
  • 批准号:
    2420942
  • 财政年份:
    2024
  • 资助金额:
    $ 27.2万
  • 项目类别:
    Standard Grant
Collaborative Research: AF: Medium: Algorithms Meet Machine Learning: Mitigating Uncertainty in Optimization
协作研究:AF:媒介:算法遇见机器学习:减轻优化中的不确定性
  • 批准号:
    2422926
  • 财政年份:
    2024
  • 资助金额:
    $ 27.2万
  • 项目类别:
    Continuing Grant
Collaborative Research: AF: Small: Structural Graph Algorithms via General Frameworks
合作研究:AF:小型:通过通用框架的结构图算法
  • 批准号:
    2347322
  • 财政年份:
    2024
  • 资助金额:
    $ 27.2万
  • 项目类别:
    Standard Grant
Collaborative Research: AF: Small: Real Solutions of Polynomial Systems
合作研究:AF:小:多项式系统的实数解
  • 批准号:
    2331401
  • 财政年份:
    2024
  • 资助金额:
    $ 27.2万
  • 项目类别:
    Standard Grant
Collaborative Research: AF: Small: Real Solutions of Polynomial Systems
合作研究:AF:小:多项式系统的实数解
  • 批准号:
    2331400
  • 财政年份:
    2024
  • 资助金额:
    $ 27.2万
  • 项目类别:
    Standard Grant
Collaborative Research: AF: Medium: Fast Combinatorial Algorithms for (Dynamic) Matchings and Shortest Paths
合作研究:AF:中:(动态)匹配和最短路径的快速组合算法
  • 批准号:
    2402283
  • 财政年份:
    2024
  • 资助金额:
    $ 27.2万
  • 项目类别:
    Continuing Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了