Lower bounds and derandomizations for branching programs

分支程序的下限和去随机化

• 批准号: RGPIN-2018-04500
• 负责人: McKenzie, Pierre
• 金额: $ 2.99万
• 依托单位: Université de Montréal
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=712661
• 关键词: Lower; bounds; derandomizations; branching; programs

GENERAL: The long-term goal of my research program is to help elucidating the structure of the complexity class P of efficiently solvable problems. In particular, can every problem in P be solved using a logarithmic amount of memory? This question predates the P versus NP question and hints at the main shortcoming of complexity theory: despite intensive efforts by a generation of researchers, no truly satisfactory lower bounds on the complexity of problems within the complexity class NP, let alone the class P, are known. SPECIFICS: In the next 5 years I will return to the study of branching programs, a computation model known to capture the memory resource. I first propose to concentrate on trying to explain why no branching program size lower bound better than quadratic is known for problems in NP. Obstacles to obtaining lower bounds on computational resources for solving a problem have been identified before. One influential notion of such an obstacle was developed by Razborov and Rudich in 1997: strong lower bounds obtained by means of what these authors named "natural proofs" were shown to rule out the existence of objects called efficient pseudorandom number generators, widely believed to exist. The empirical fact that many of our best current complexity lower bounds were obtained by natural proofs is thus an obstacle in the above sense. The last 25 years have seen much research on pseudo-randomness in the context of memory-bounded computation. I am hoping to draw from this work in order to define the equivalent of natural proofs against (say) cubic size lower bounds for branching programs and to derive unlikely derandomization consequences. I will explore possible variants of natural proofs involving the recently introduced notion of pseudo-deterministic computation. I will investigate derandomization of bounded-width branching programs under the guidance of algebraic automata theory. I will consider probabilistic variants of restricted branching programs (such as monotone or incremental) and analyse their expressivity and their derandomizations. SIGNIFICANCE: Rigorously proving computational complexity lower bounds can be very useful. A famous example arises in cryptography, where the current lack of computational hardness proofs prevents ruling out that a clever individual or organization might break into communication channels thought to be secure. Other examples follow from a 30-year-old discovery by now exploited extensively: if certain computational problems could be proved hard, then tools to construct pseudorandom number generators would follow; such tools in turn could serve to transform known efficient probabilistic algorithms into equally efficient deterministic (hence freed from the uncertainty that accompanies the reliance on random bits) algorithms. Searching for obstacles to proving lower bounds could as well suggest new ways to improve existing algorithms.

概述： 我的研究计划的长期目标是帮助阐明有效可解问题的复杂性类P的结构。特别是，P中的每个问题都可以使用对数数量的内存来解决吗？这个问题早于P与NP问题，并暗示了复杂性理论的主要缺陷：尽管一代研究人员付出了巨大的努力，但在复杂性类NP中，没有真正令人满意的问题复杂性下限，更不用说P类了。 规格： 在接下来的5年里，我将回到分支程序的研究中，这是一种已知的捕获内存资源的计算模型。我首先建议集中精力试图解释为什么没有分支程序大小下限比二次已知的NP问题。以前已经确定了获得用于解决问题的计算资源的下限的障碍。1997年，Razborov和Rudich提出了一个关于这种障碍的有影响力的概念：通过这些作者称为"自然证明"的方法获得的强下界被证明排除了被称为有效伪随机数生成器的对象的存在，人们普遍认为存在。因此，经验事实是，我们当前许多最好的复杂度下限都是通过自然证明获得的，这在上述意义上是一个障碍。 在过去的25年里，在内存有限计算的背景下，对伪随机性进行了大量的研究。 我希望从这项工作，以定义等价的自然证明对（说）立方尺寸下界的分支程序，并得出不太可能去随机化的后果。我将探讨涉及最近引入的伪确定性计算概念的自然证明的可能变体。我将在代数自动机理论的指导下研究有界宽度分支程序的去随机化。我将考虑限制分支程序的概率变体（如单调或增量），并分析它们的表达性和去随机化。 重要性： 严格证明计算复杂度下限是非常有用的。一个著名的例子出现在密码学中，目前缺乏计算硬度证明，无法排除聪明的个人或组织可能闯入被认为是安全的通信渠道。其他例子来自一个30年前的发现，现在已经被广泛利用：如果某些计算问题可以被证明是困难的，那么构建伪随机数生成器的工具就会随之而来;这些工具反过来可以将已知的有效概率算法转换为同样有效的确定性算法（因此摆脱了依赖随机位的不确定性）。寻找证明下界的障碍也可以提出改进现有算法的新方法。