AF:Small: Derandomization and Lower Bounds

计算在社会中无处不在，随机性扮演着重要的角色，既是一种负担，也是一种商品。特别是，抛硬币的能力在大量的计算设置中似乎非常有用，计算理论的一个中心研究线试图确定其实际能力。在这种背景下，研究人员开发了尽可能高效的随机过程的确定性模拟。规范的方法需要构造伪随机生成器，这是一种有效的确定性过程，可以将一个短的随机抛硬币序列延伸到一个更长的序列，而这个序列在研究过程中看起来仍然是随机的。该项目的驱动问题是，这种规范方法是否万能，或者是否存在更好的方法来获得确定性模拟。该项目侧重于非随机化、伪随机生成器和下界之间的关系。已知有效伪随机生成器的存在等价于某些类型的电路下界（其保持开放）。也有一些结果表明，非随机化意味着某种形式的电路下界，但下界通常不够强，因此暗示回相同的非随机化。该项目的一个主要推力是建立电路下界和非随机化之间的等价关系，这意味着通过伪随机生成器的规范非随机化是全能的。PI和他的同事已经开发了一个框架来获得这样的结果，并打算将其应用于大型随机过程，包括被称为Arthur-Merlin游戏的有效决策过程和有效验证过程。主要焦点在于非随机化的标准概念，其中模拟需要在任何地方都是正确的，但PI也将考虑较弱的概念，其中确定性模拟允许在某些输入上出错。除了进一步加深我们对计算中随机性力量的认识外，该项目旨在为该主题和更广泛的计算复杂性领域的研究生提供培训。

Computation is omnipresent in society, and randomness plays an important role, both as a liability and as a commodity. In particular, the ability to flip fair coins seems surprisingly useful in a plethora of computational settings, and a central line of research in the theory of computing tries to determine its actual power. In that context researchers develop deterministic simulations of randomized processes that are as efficient as possible. The canonical approach entails the construction of pseudo-random generators, which are efficient deterministic procedures that stretch a short random coin flip sequence to a much longer sequence that still looks random to the process under investigation. The driving question of the project is whether this canonical approach is omnipotent or whether there exist better ways to obtain deterministic simulations.The project focuses on the relationships between derandomization, pseudo-random generators, and lower bounds. The existence of efficient pseudo-random generators is known to be equivalent to certain types of circuit lower bounds (which remain open). There are also a number of results showing that derandomization implies circuit lower bounds of some sort, but the lower bounds are typically not strong enough so as to imply back the same derandomization. A major thrust of the project is to establish equivalences between circuit lower bounds and derandomization, implying that canonical derandomization through pseudo-random generators is omnipotent.The PI and his coworkers have developed a framework for deriving such results, and intend to apply it to large classes of randomized processes, including efficient decision procedures and efficient verification processes known as Arthur-Merlin games. The main focus lies on the standard notion of derandomization, in which the simulation needs to be correct everywhere, but the PI will as well consider weaker notions in which the deterministic simulation is allowed to err on some inputs.Apart from furthering our knowledge about the power of randomness in computation, the project aims to provide graduate training on that topic and in the broader area of computational complexity.