Proving and 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.