Proving and Using Pseudorandomness

证明和使用伪随机性

• 批准号: 1639631
• 负责人: Richard Karp
• 金额: $ 2万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-07-01 至 2017-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1639631&HistoricalAwards=false
• 关键词: Proving; Using; Pseudorandomness

Notions of pseudorandomness and quasirandomness have been developed and investigated in several areas of theoretical computer science, combinatorics and number theory (including complexity theory, cryptography, graph theory, additive combinatorics and analytic number theory) to answer such questions such as the following. What does it mean for a fixed object to be "random-like"? Is it possible to turn existence proofs that use the probabilistic method into explicit constructions? Is it possible to simulate randomized algorithms deterministically? When can heuristic arguments that treat the primes as a random set of integers be turned into rigorous proofs? In the setting of additive combinatorics, what is the minimal set of tests that primes have to satisfy in order to guarantee that they contain arithmetic progressions (or other structures)?At a very high level, the appeal of such notions is that one can easily prove that certain properties are true for random objects, using probabilistic methods, and then transfer such properties to pseudorandom objects, provided that the pseudorandomness ?fools? the probabilistic techniques. A theme of this workshop will be how to leverage weak pseudorandomness properties, fooling simple classes of tests, in order to derive stronger pseudorandomness properties related to more complex tests. The workshop will explore unconditional constructions of pseudorandom objects at the frontier of progress, such as pseudorandom generators for small-space computations, small-depth circuits with modular gates, threshold circuits, and formulas in disjunctive normal form.The workshop will bring together complexity theorists, combinatorial mathematicians, number theorists, probabilists and algorithm designers interested in the foundations and uses of pseudo-randomness. It will be open to all potential participants, and the workshop findings (including videorecordings of presentations) will be distributed to the public for comment and engagement. The organizers will encourage students to attend the workshop, and will actively recruit scientists from a diversity of backgrounds to contribute to a wide range of applications.

伪随机性和拟随机性的概念已经在理论计算机科学、组合学和数论（包括复杂性理论、密码学、图论、加法组合学和解析数论）的若干领域中得到发展和研究，以回答诸如以下的问题。一个固定的对象是“类随机”的是什么意思？有没有可能将使用概率方法的存在性证明转化为显式构造？有可能确定性地模拟随机算法吗？什么时候可以将素数视为随机整数集的启发式论点转化为严格的证明？在加法组合学中，素数必须满足的最小测试集是什么，以保证它们包含算术级数（或其他结构）？在一个非常高的水平上，这种概念的吸引力是，人们可以很容易地证明，某些属性是真实的随机对象，使用概率的方法，然后将这些属性转移到伪随机对象，只要伪随机性？傻瓜？概率技术。本次研讨会的主题将是如何利用弱伪随机属性，愚弄简单的测试类，以获得更强的伪随机属性相关的更复杂的测试。研讨会将探讨伪随机对象的无条件构造，如用于小空间计算的伪随机发生器、具有模块门的小深度电路、阈值电路和析取范式公式。研讨会将汇集对伪随机的基础和用途感兴趣的复杂性理论家、组合数学家、数论家、概率学家和算法设计师。研讨会将向所有潜在的与会者开放，研讨会的结果（包括发言的录像）将分发给公众，供其发表意见和参与。组织者将鼓励学生参加研讨会，并将积极招募来自不同背景的科学家，为广泛的应用做出贡献。