**Average-case complexity of detecting cliques**(5 March 2013, 16 Uhr, Seminarraum S 307, Robert Mayer Strasse 11-15)

**Abstract:**
Erdos-Renyi random graphs are believed to be a source of hard instances for clique problems. While the random graph $G(n,1/2)$ almost surely contains
cliques of size $\sim ~2\log n$, Karp in 1976 conjectured that no
polynomial-time algorithm finds a clique larger than $(1+\epsilon)\log n$.
As a tiny step toward this conjecture, we show (tight) lower bounds on
the average-case complexity of the $k$-clique problem in two well-studied
classes of circuits: bounded-depth
($AC^0$) circuits and monotone circuits. As a corollary, we obtain the first
"size hierarchy" theorem for $AC^0$ and a related result for first-order logic.

Currently, Ben is a postdoc at Tokyo Institute of Technology. [Update: currently at Duke University.] Previously, he was graduate student in the Theory of Computation group in MIT's Computer Science and Artificial Intelligence Laboratory where he was advised by Madhu Sudan. His main research interests are circuit complexity and finite model theory.

During the last several years, Ben made at least two major contributions
in the circuit complexity (presented at STOC 2008 and FOCS 2010).
So far, explicit lower bounds for various types
of circuits were *worst case* bounds: every ``too small'' circuit $C(x)$
for a given boolean function $f(x)$ must make an error, that is, $C(x)\neq f(x)$
for at least one input vector $x$. But such a proof does not say the whole truth:
it may well be that small circuits are still good in average
(for most input vectors). Say, the (now classical) lower bound of Razborov
(inproved later by Alon and Boppana) states that no monotone circuit with
much fewer than $n^k$ can solve the $k$-Clique problem
on *all* $n$-vertex graphs. On the other hand,
a monotone circuit implementing a simple greedy algorithm can solve this
problem on *average* by using only about $n^{k/4}$ gates.
What Ben proved is that this is actually the best we can do: every monotone
circuit solving the $k$-Clique problem on average must
have at least about $n^{k/4}$ gates. His idea is to show that, if we randomly
insert a $k$-clique into an input graph without $k$-cliques, then
with high probability, a small circuit will not detect the difference!
To realize this idea, he invented some
new tools -- like the ``approximate version'' of the Sunflower Lemma --
that are of independent interest.

Before this result, he proved that also (non-monotone) constant depth circuits of size $n^{k/4}$ cannot approximate $k$-Clique as well. Important here is that his lower bound does not have the actual depth $d$ in the exponent: previous lower bounds were of the form $n^{k/d^2}$.

March 2013