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.
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}$.