AF:Small: Derandomization and Lower Bounds

AF:Small：去随机化和下界

• 批准号: 1319822
• 负责人: Dieter van Melkebeek
• 金额: $ 40万
• 依托单位: University of Wisconsin-Madison
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-09-15 至 2018-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1319822&HistoricalAwards=false
• 关键词: AF; Small; Derandomization; Lower; Bounds

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.

计算在社会中无处不在，随机性发挥着重要作用，无论是作为一种责任还是一种商品。特别是，翻转公平硬币的能力在大量的计算环境中似乎出人意料地有用，并且计算理论的研究中心线试图确定其实际能力。在这种背景下，研究人员开发了尽可能高效的随机过程的确定性模拟。规范方法需要构建伪随机生成器，这是一种有效的确定性程序，可将短随机硬币翻转序列拉伸为更长的序列，该序列对于所研究的过程来说仍然看起来是随机的。该项目的驱动问题是这种规范方法是否是万能的，或者是否存在更好的方法来获得确定性模拟。该项目重点关注去随机化、伪随机生成器和下界之间的关系。已知有效伪随机生成器的存在等同于某些类型的电路下界（保持开放）。还有许多结果表明，去随机化意味着某种电路下限，但下限通常不够强，不足以暗示相同的去随机化。该项目的一个主要目标是在电路下界和去随机化之间建立等价关系，这意味着通过伪随机生成器的规范去随机化是万能的。PI 和他的同事开发了一个用于导出此类结果的框架，并打算将其应用于大型随机过程的类别，包括称为亚瑟梅林游戏的有效决策过程和有效验证过程。主要焦点在于去随机化的标准概念，其中模拟需要在任何地方都是正确的，但 PI 也会考虑较弱的概念，其中允许确定性模拟在某些输入上出错。计算随机性的力量，该项目旨在提供有关该主题以及更广泛的计算复杂性领域的研究生培训。