DIMACS Seminar


Potential of the Approximation Method


Akira Maruoka
Graduate School of Information Sciences, Tohoku University
Aoba-ku Sendai 980-77, Japan


Seminar Room 431, CoRE Building,
Busch Campus, Rutgers University.


2:00 PM
Friday, October 11, 1996

Developing some 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^{\mbox{min}(\sqrt{s-1}/2, m/(4s))}$ gates: If a non-monotone circuit computes CLIQUE using a ``small" amount of negation, then the circuit contains an exponential number of gates. The former is proved very simply using so called bottleneck counting argument within the framework of approximation, whereas the latter is verified introducing a notion of restricting negation and generalizing the sunflower contraction.

Document last modified on September 23, 1996