k-Subgraph Isomorphism on AC_0 Circuits

Recently, Rossman [STOC ´08] established a lower bound of omega(n^k/4) on the size of constant-depth circuits for the k-clique function on n-vertex graphs, which is the first lower bound that does not depend on the depth of circuits in the exponent of n. He showed, in fact, a stronger statement: Suppose f_n : {0, 1}^(n/2) rarr {0,1} is a sequence of functions computed by constant-depth circuits of size O(n^t). For any positive integer k and 0 < alpha les 1/(2t - 1), let G = ER(n, n^-alpha) be an Erdos-Renyi random graph with edge probability n^-alpha and let K_A be a k-clique on a uniformly chosen k vertices of G. Then f_n(G) = f_n(G cup K_A) asymptotically almost surely. In this paper, we prove that this bound is essentially tight by showing that there exists a sequence of Boolean functions f_n : {0, 1}^(n/2) rarr {0, 1} that can be computed by constant-depth circuits of size O(n^t) such that f_n(G) ne f_n(G cup K_A) asymptotically almost surely for the same distributions with alpha = 1/(2t - 5.5) and k = 4t - c (where c is a small constant independent of k). This means that there are constant-depth circuits of size O(n^(k/4+c)) that correctly compute the k-clique function with high probability when the input is a random graph with independent edge probability around n^-2/(k-1). Several extensions of his lower bound method to the problem of detecting general patterns as well as some upper bounds are also described. In addition, we provide an explicit construction of DNF formulas that are almost incompressible by any constant-depth circuits.