The Constant-Depth Complexity of k-Clique

COMPUTER SCIENCE/DISCRETE MATH I
Topic:The Constant-Depth Complexity of k-Clique
Speaker:Ben Rossman
Affiliation:Massachusetts Institute of Technology
Date:Monday, April 20
Time/Room:11:15am - 12:15pm/S-101

I will discuss a lower bound of $\omega(n^(k/4))$ on the size of constant-depth $(AC_0)$ circuits solving the k-clique problem on n-vertex graphs. This bound follows from a stronger result that $AC_0$ circuits of size $O(n^(k/4))$ almost surely fail to distinguish between an Erdos-Renyi random graph $G$ at the k-clique threshold and $G' = G \cup$(random k-clique). This lower bound is nearly matched by a recent construction of Amano of $AC_0$ circuits of size $O(n^((k/4)+const.))$ which almost surely distinguish $G$ from $G'$ . I will also discuss a corollary in logic: strictness of the "variable hierarchy" for first-order logic on ordered graphs.