The Potential of the Approximation Method
Kazuyuki Amano, Akira Maruoka · SIAM Journal on Computing · 2004
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 \leq s \leq m/4$, a monotone circuit computing CLIQUE$(m,s)$ contains at least $(1/2)1.8^{\min(\sqrt{s-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.