k-SUBGRAPH ISOMORPHISM ON AC0 CIRCUITS

Recently, Rossman (STOC '08) established a lower bound of w(n(k/4)) on the size of constant-depth circuits computing the k-clique function on n-vertex graphs for any constant k. This 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)) -> {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 <= 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 boolean OR 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 fn : {0, 1}((n)(2)) -> {0, 1} that can be computed by constant-depth circuits of size O( nt) such that f(n)(G) not equal f(n)(G boolean OR K-A) asymptotically almost surely for the same distributions with alpha - 1/(2t - 9.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 Rossman's 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.