New Directions in Complexity Theory

计算复杂性研究计算的内在限制，包括时间、空间、随机性和不确定性等资源，以及这些资源是如何相关的。证明复杂性(对命题证明的研究)与复杂性理论密切相关：从通信复杂性和电路复杂性出发的方法被大量用于获得证明复杂性下界，反过来，证明复杂性下界可以用来排除求解优化问题的大类自然算法。我建议攻击复杂性理论和证明复杂性的几个新方向。在最近的工作中，我们发展了通信复杂性的难度递增方法，并用该方法证明了各种新的电路下界(即最著名的单调深度下界，以及单调跨度程序和秘密共享方案的第一个指数大小的下界)。到目前为止，这是相当成功的，还有许多问题有待研究。例如，我们想要证明随机化(BPP)通信的一个难度递增定理，该定理应该导致新的电路下界。其次，我想证明分支程序和比较电路的超二次下界，打破了自1960年S以来的长期存在的障碍。第三，在证明复杂性方面，我想证明割平面证明系统(以及相关的矩阵切割系统)的尺寸下界，并进一步发展我在Grochow开始的代数电路复杂性和证明复杂性之间的一个新的联系。利用这种方法，我希望证明AC0[p]-Frege系统的下界，这是一个长期存在的证明复杂性的公开问题。

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.