Average-case complexity of detecting cliques
Madhu Sudan, Benjamin Rossman · 2010
The computational problem of testing whether a graph contains a complete subgraph of size k is among the most fundamental problems studied in theoretical computer science. This thesis is concerned with proving lower bounds for k-CLIQUE, as this problem is known. Our results show that, in certain models of computation, solving k-CLIQUE in the average case requires Ω( nk/4) resources (moreover, k/4 is tight). Here the models of computation are bounded-depth Boolean circuits and unbounded-depth monotone circuits, the complexity measure is the number of gates, and the input distributions are random graphs with an appropriate density of edges. Such random graphs (the well-studied Erdos-Renyi random graphs) are widely believed to be a source of computationally hard instances for clique problems (as Karp suggested in 1976). Our results are the first unconditional lower bounds supporting this hypothesis. For bounded-depth Boolean circuits, our average-case hardness result significantly improves the previous worst-case lower bounds of Ω( nk/poly( d)) for depth-d circuits. In particular, our lower bound of Ω(n k/4) has no noticeable dependence on d for circuits of depth d ≤ k −2 log n/log log n, thus bypassing the previous size-depth tradeoffs. As a consequence, we obtain a novel Size Hierarchy Theorem for uniform AC0. A related application answers a longstanding open question in finite model theory (raised by Immerman in 1982): we show that the hierarchy of bounded-variable fragments of first-order logic is strict on finite ordered graphs. Additional results of this thesis characterize the average-case descriptive complexity of k-CLIQUE through the lens of first-order logic. (Copies available exclusively from MIT Libraries, Rm. 14-0551, Cambridge, MA 02139-4307. Ph. 617-253-5668; Fax 617-253-1690.)