Average-Case Lower Bounds in Boolean Circuit Complexity

复杂性理论研究高效计算的本质和局限性。最终目标是下界，表明基本问题，如CLIQUE和STCONN，不能用有限的计算资源，如多项式时间或对数内存来解决。电路复杂性的子域试图证明计算的组合模型的下界。在这些模型中，布尔电路(由AND、OR和NOT门组成)是最基本和最重要的，因为它们为解决P与NP问题提供了一条具体的途径：人们只需要证明团问题(或NP中的任何其他问题)的超多项式电路大小下界。然而，经过60多年的努力，已知的最强下限只是线性的。 为了发展更敏锐的见解和技术，电路复杂性的大部分研究集中在有限类的布尔电路(如公式、有界深度电路和单调电路)。在80年代的S和90年代的S出现了开创性的下限之后，随着现有技术似乎达到了极限，进展放缓。Razborov和Rudich(1997)的“自然证明障碍”指出了进一步发展的形式障碍，它表明针对更强大的布尔电路类的下界只能来自于被磨练成特定的难以计算的函数的技术，同时避免了几乎所有函数共享的一般性质。 这项研究提案旨在通过一套针对基本问题(包括CLIQUE和STCONN)量身定做的新技术，在电路复杂性方面取得重大进展。作者在以前的工作中介绍的一种很有前途的方法，提供了一个组合解释为什么小布尔公式无法检测Erdosrényi随机图中的长路径。这种方法已经产生了突破性的下限。拟议中的研究将继续进行一系列后续步骤，雄心勃勃的目标是证明相对于布尔公式的超多项式下界。这将解决复杂性理论中的一个重大悬而未决的问题(将NC1与P分开)。除了这一雄心勃勃的目标，该提案还探索了布尔电路复杂性以及与证明复杂性和通信复杂性等领域的联系的其他有前途的研究方向。

Complexity Theory studies the nature and limits of efficient computation. The ultimate goals are lower bounds showing that fundamental problems, such as CLIQUE and STCONN, cannot be solved with limited computational resources, such as polynomial time or logarithmic memory. The subfield of Circuit Complexity seeks to prove lower bounds in combinatorial models of computation. Among these models, Boolean circuits (composed of AND, OR and NOT gates) are the most elemental and important, as they offer a concrete path to resolving the P versus NP question: one need only prove a super-polynomial circuit-size lower bound for the CLIQUE problem (or any other problem in NP). However, after over 60 years of effort, the strongest known lower bounds are only linear. With the aim of developing sharper insights and techniques, the majority of the research in Circuit Complexity has focused on restricted classes of Boolean circuits (such as formulas, bounded-depth circuits, and monotone circuits). Following a burst of seminal lower bounds in the 80's and 90's, progress slowed as the existing techniques appeared to reach their limits. The “Natural Proofs barrier” of Razborov and Rudich (1997) identifies a formal roadblock to further progress by showing that lower bounds against more powerful classes of Boolean circuits can only proceed from techniques that are honed to specific hard-to-compute functions, while avoiding the generic properties shared by almost all functions. This research proposal aims for a major advance in Circuit Complexity through a set of new techniques tailored to fundamental problems including CLIQUE and STCONN. One promising approach, introduced in previous work of the author, provides a combinatorial explanation of why small Boolean formulas fail to detect long paths in ErdosRényi random graphs. This approach has already produced groundbreaking lower bounds. The proposed research will pursue a sequence of next steps, with the ambitious goal of proving a super-polynomial lower bound against Boolean formulas. This would resolve a significant open problem in Complexity Theory (separating NC1 from P). Alongside this ambitious goal, this proposal explores other promising directions of research in Boolean circuit complexity and connections to areas such as proof complexity and communication complexity.