Abstract | ||
---|---|---|
We prove a lower bound of ω(nk/4) on the size of constant-depth circuits solving the k-clique problem on n-vertex graphs (for every constant k). This improves a lower bound of ω(nk/89d2) due to Beame where d is the circuit depth. Our lower bound has the advantage that it does not depend on the constant d in the exponent of n, thus breaking the mold of the traditional size-depth tradeoff. Our k-clique lower bound derives from a stronger result of independent interest. Suppose fn :0,1n/2 → {0,1} is a sequence of functions computed by constant-depth circuits of size O(nt). Let G be an Erdos-Renyi random graph with vertex set {1,...,n} and independent edge probabilities n-α where α ≤ 1/2t-1. Let A be a uniform random k-element subset of {1,...,n} (where k is any constant independent of n) and let KA denote the clique supported on A. We prove that fn(G) = fn(G ∪ KA) asymptotically almost surely. These results resolve a long-standing open question in finite model theory (going back at least to Immerman in 1982). The m-variable fragment of first-order logic, denoted by FOm, consists of the first-order sentences which involve at most m variables. Our results imply that the bounded variable hierarchy FO1 ⊂ FO2 ⊂ ... ⊂ FOm ⊂ ... is strict in terms of expressive power on finite ordered graphs. It was previously unknown that FO3 is less expressive than full first-order logic on finite ordered graphs. |
Year | DOI | Venue |
---|---|---|
2008 | 10.1145/1374376.1374480 | STOC |
Keywords | Field | DocType |
first-order sentence,constant-depth complexity,independent interest,full first-order logic,constant k,constant-depth circuit,erdos-renyi random graph,expressive power,independent edge probabilities n,first-order logic,finite model theory,circuit complexity,first order logic,lower bound | Discrete mathematics,Combinatorics,Finite model theory,Random graph,Exponent,Clique,Vertex (geometry),Upper and lower bounds,Almost surely,Mathematics,Bounded function | Conference |
ISSN | Citations | PageRank |
0737-8017 | 32 | 1.35 |
References | Authors | |
18 | 1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Benjamin Rossman | 1 | 298 | 20.00 |