课题基金 / 基金详情

AF: Small: The Power of Randomness in Decision and Verification

AF: Small: The Power of Randomness in Decision and Verification
AF:小:决策和验证中随机性的力量
批准号:
2312540
负责人:
Dieter van Melkebeek
金额:
$60.0万
依托单位国家:
美国
项目类别:
Standard Grant
财政年份:
2023
资助国家:
美国
项目状态:
未结题
起止时间:
2023-05-01 至 2026-04-30

项目摘要

项目成果

Dieter van Melkebeek的其他基金

相似基金

相关文献

中文摘要
翻译
随机选择的能力似乎简化了一些计算任务。例如,为了确定像x*x-y*y和(x+y)*(x-y)这样的两个公式是否等价,只需为x和y插入随机值,并验证两个公式是否产生相同的值。即使对于复杂的公式,这也是一种可靠的策略,比操作抽象公式更容易。随机性的一种更复杂的用法包括一种抽查计算的方法,这种方法比执行计算本身所需的工作量要少得多——在将计算委托给云计算的时代,这是一种至关重要的特性。这个项目研究了在没有随机性的情况下,在决策和验证中实现类似效率的潜力。它结合了研究生和本科生的培训和教育,并包括编写一本教科书,使计算思维和量子算法领域更容易为更广泛的公众所接受。该项目探索了非随机化领域的两个新方向。在有界误差多项式时间决策过程(即有界误差概率多项式时间类,BPP)的设置中,研究人员提出了一种基于消失理想概念的非随机化多项式恒等式检验(PIT)的原则方法。PIT捕获了上述公式等价问题,并在非随机化领域发挥了核心作用,因为已知的结果表明,非随机化PIT可以使所有BPP非随机化。研究人员已经描述了广泛应用于PIT的伪随机发生器的消失理想,计划开发其他发生器的方法,并研究其后果。在被称为Arthur-Merlin (AM)协议的多项式时间交互验证过程的设置中,研究人员希望进一步发展下界和非随机化之间的联系,特别是通过适应最近为BPP设置建立的AM实例连接的设置。该奖项反映了美国国家科学基金会的法定使命,并通过使用基金会的知识价值和更广泛的影响审查标准进行评估,被认为值得支持。
英文摘要
The ability to make random choices seems to simplify several computational tasks. For example, in order to decide whether two formulas like x*x-y*y and (x+y)*(x-y) are equivalent, one can merely plug in random values for x and y and verify whether the two formulas yield the same value. Even for complicated formulas, this is a reliable strategy, easier than manipulating the abstract formulas. A more involved use of randomness consists of a way to spot-check computations that requires significantly less effort than performing the computations themselves---a feature of paramount importance in the day and age of delegating computations to the cloud. This project investigates the potential of achieving similar efficiency in decision and verification without randomness. It incorporates graduate and undergraduate training and education, and includes the development of a textbook that makes computational thinking and the area of quantum algorithms more accessible to a broader public.The project explores two new directions in the area of derandomization. In the setting of polynomial-time decision procedures with bounded error (i.e., bounded-error probabilistic polynomial time class, BPP), the investigators propose a principled approach towards derandomizing Polynomial Identity Testing (PIT) based on the notion of a vanishing ideal. PIT captures the above formula equivalence problem and plays a central role in the area of derandomization as known results suggest that derandomizing PIT may enable derandomizing all of BPP. The investigators already characterized the vanishing ideal of a widely used pseudorandom generator for PIT, plan to develop the approach for other generators, and to research the ramifications. In the setting of polynomial-time interactive verification processes known as Arthur-Merlin (AM) protocols, the investigators want to further develop the connections between lower bounds and derandomization, in particular by adapting to the setting of AM the instance-wise connection that was recently established for the setting of BPP.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.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
AF: EAGER: The Power of Isolation in Computing
  • 批准号:
    1838434
  • 项目类别:
    Standard Grant
  • 资助金额:
    $12.5万
  • 财政年份:
    2018
  • 负责人:
    Dieter van Melkebeek
  • 依托单位:
CCF: AF: Student Travel Support for the IEEE Conference on Computational Complexity 2014
  • 批准号:
    1415168
  • 项目类别:
    Standard Grant
  • 资助金额:
    $1.5万
  • 财政年份:
    2013
  • 负责人:
    Dieter van Melkebeek
  • 依托单位:
AF:Small: Derandomization and Lower Bounds
  • 批准号:
    1319822
  • 项目类别:
    Standard Grant
  • 资助金额:
    $40.0万
  • 财政年份:
    2013
  • 负责人:
    Dieter van Melkebeek
  • 依托单位:
AF:Small: Applications of AP-free sets and derandomization
  • 批准号:
    1017597
  • 项目类别:
    Standard Grant
  • 资助金额:
    $49.99万
  • 财政年份:
    2010
  • 负责人:
    Dieter van Melkebeek
  • 依托单位:
国内基金
海外基金
昼夜节律性small RNA在血斑形成时间推断中的法医学应用研究
  • 批准号:
  • 项目类别:
    省市级项目
  • 资助金额:
    --
  • 批准年份:
    2024
  • 负责人:
  • 依托单位:
tRNA-derived small RNA上调YBX1/CCL5通路参与硼替佐米诱导慢性疼痛的机制研究
  • 批准号:
  • 项目类别:
    省市级项目
  • 资助金额:
    10.0万元
  • 批准年份:
    2022
  • 负责人:
    张祥忠
  • 依托单位:
Small RNA调控I-F型CRISPR-Cas适应性免疫性的应答及分子机制
Small RNAs调控解淀粉芽胞杆菌FZB42生防功能的机制研究
  • 批准号:
    31972324
  • 项目类别:
    面上项目
  • 资助金额:
    58.0万元
  • 批准年份:
    2019
  • 负责人:
    高学文
  • 依托单位: