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

AF：小：决策和验证中随机性的力量

• 批准号: 2312540
• 负责人: Dieter van Melkebeek
• 金额: $ 60万
• 依托单位: University of Wisconsin-Madison
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-05-01 至 2026-04-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2312540&HistoricalAwards=false
• 关键词: AF; Small; Power; Randomness; Decision

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.

做出随机选择的能力似乎简化了几个计算任务。例如，为了确定两个公式（例如x*x-y*y和（x+y）*（x-y））是否等效，一个人只能插入x和y的随机值，并验证两个公式是否产生相同的值。即使对于复杂的公式，这也是一个可靠的策略，比操纵抽象公式更容易。与随机性的使用更重要的是，与执行计算本身相比，需要更少的精力来检查计算的方法 - 在将计算委派计算到云中至关重要的特征。该项目研究了在没有随机性的情况下实现决策和验证效率相似的潜力。它结合了研究生和本科培训和教育，并包括一本教科书的开发，该教科书使计算思维和量子算法的领域更容易被更广泛的公众访问。该项目探讨了衍生物化领域的两个新方向。在设置具有有界误差的多项式时间决策过程中（即有界错误的概率多项式时间类别，BPP），研究人员提出了一种基于一个消失的理想的概念，提出了一种原则性的方法，以驱散多项式身份测试（PIT）。坑捕获上述公式等效问题，并在降低的区域中起着核心作用，因为已知的结果表明，降低的坑可能会使所有BPP降低。研究人员已经表征了广泛使用的伪随机生成器的消失的理想，计划为其他发电机开发方法，并研究后果。 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 标准。