Algorithms and Complexity Seminar

Thursday, November 8, 2007, 4-5:15pm in 32-G575.

On the constant-depth complexity of k-clique

Ben Rossman (MIT)

I will discuss a recent result that constant-depth circuits deciding the k-clique problem require \Omega(n^(2k/9)) size. This result appears to be the first which establishes that the AC^0 size hierarchy (of circuit classes Size-Depth(O(n^t),O(1)) parameterized by t >= 0) does not collapse. It is obtained by a stronger assertion that may be of independent interest. Let P be a property of finite labeled graphs which is defined by constant-depth circuits of size O(n^t), and let G be an Erdos-Renyi random graph on n vertices where each edge is independently included with probability n^(-t/9). We prove that, for every constant k, the event "G \in P iff (G + a random k-clique) \in P" holds aymptotically almost surely for large n.

Host: Madhu Sudan

(The Algorithms and Complexity Seminar series talks are usually held Thursdays from 4-5:15pm in 32-G575.)