The potential of the approximation method
Developing certain techniques for the approximation method, we establish precise versions of the following statements concerning lower bounds for circuits that detect cliques of size s in a graph with m vertices: For 5 less than or equal to s less than or equal to m/4, a monotone circuit computing CLIQUE(m, s) contains at least (1/2)1.8(min(roots-1/2, m/(4s))) gates: If a nonmonotone circuit computes CLIQUE using a "small" amount of negation, then the circuit contains an exponential number of gates. The former is proved by using so-called bottleneck counting argument within the framework of approximation, and the latter is verified by introducing a notion of restricting negation in circuits and generalizing these arguments to nonmonotone cases.
approximation method lower bounds monotone circuit circuit complexity clique function negation-limited circuit