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也会考虑较弱的概念，其中确定性模拟允许在某些输入上出错。除了进一步了解计算中随机性的力量之外，该项目旨在提供有关该主题和更广泛的计算复杂性领域的研究生培训。