Average-Case Lower Bounds in Boolean Circuit Complexity

点击翻译按钮获取中文摘要

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.**