# DIMACS Seminar

## Title:

Potential of the Approximation Method

## Speaker:

- Akira Maruoka
- Graduate School of Information Sciences, Tohoku University
- Aoba-ku Sendai 980-77, Japan
- maruoka@ecei.tohoku.ac.jp

## Place:

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

## Time:

- 2:00 PM
- Friday, October 11, 1996

Abstract:
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.

dimacs-www@dimacs.rutgers.edu
Document last modified on September 23, 1996