New Directions in Complexity Theory

复杂性理论的新方向

• 批准号: RGPIN-2017-06399
• 负责人: Pitassi, Toniann
• 金额: $ 4.37万
• 依托单位: University of Toronto
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2017
• 资助国家: 加拿大
• 起止时间: 2017-01-01 至 2018-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=634422
• 关键词: New; Directions; Complexity; Theory

Computational complexity studies the inherent limits of computation, in terms of resources such as time, space, randomness, and nondeterminism, and how these resources are related. Proof complexity (the study of propositional proofs) is tightly connected to complexity theory: methods from communication complexity and circuit complexity have been heavily used to obtain proof complexity lower bounds, and conversely lower bounds in proof complexity can be used to rule out large classes of natural algorithms for solving optimization problems. I propose to attack several new directions in complexity theory and proof complexity. In recent work we have developed the hardness escalation method in communication complexity, and used this method to prove a variety of new circuit lower bounds (i.e., the best known monotone depth lower bounds, as well as the first exponential-size lower bounds for monotone span programs and secret sharing schemes.) This has been quite successful so far, and many problems remain to be studied. For example, we would like to prove a hardness escalation theorem for randomized (BPP) communication, which should lead to new circuit lower bounds. Secondly, I want to prove super-quadratic lower bounds for branching programs and comparator circuits, breaking the longstanding barrier from the 1960's. Thirdly, in proof complexity, I want to prove size lower bounds for Cutting Planes proof systems (and related matrix cut systems), and I want to further develop a new connection between algebraic circuit complexity and proof complexity that I initiated with Grochow. Using this approach, I hope to prove lower bounds for AC0[p]-Frege systems, a long-standing open problem in proof complexity.

计算复杂性研究计算的内在限制，包括时间、空间、随机性和非确定性等资源，以及这些资源之间的关系。证明复杂性（对命题证明的研究）与复杂性理论紧密相连：通信复杂性和电路复杂性的方法被大量用于获得证明复杂性的下限，相反，证明复杂性的下限可以用来排除解决优化问题的大量自然算法。我建议攻击复杂性理论和证明复杂性的几个新方向。在最近的工作中，我们开发了通信复杂性的硬度升级方法，并使用该方法证明了各种新的电路下界（即，最著名的单调深度下界，以及单调跨度程序和秘密共享方案的第一指数大小下界。这一做法迄今已取得了相当的成功，但仍有许多问题有待研究。例如，我们想证明随机（BPP）通信的硬度升级定理，这应该会导致新的电路下界。其次，我想证明分支程序和比较器电路的超二次下界，打破20世纪60年代长期存在的障碍。第三，在证明复杂性方面，我想证明切割平面证明系统（以及相关的矩阵切割系统）的大小下限，我想进一步发展代数电路复杂性和证明复杂性之间的新联系，这是我与Grochow一起发起的。使用这种方法，我希望证明AC 0 [p]-Frege系统的下界，这是一个长期存在的证明复杂性的公开问题。