Skip to main content

On the constant-depth complexity of k-clique

Publication ,  Conference
Rossman, B
Published in: Proceedings of the Annual ACM Symposium on Theory of Computing
January 1, 2008

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/59d2) 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-elique lower bound derives from a stronger result of independent interest. Suppose fn : {0, l} n(n/2)→ {0, l} is a sequence of functions computed by constant-depth circuits of size O(nt). Let G be an Erdös-Rényi random graph with vertex set {1, . . . , n} and independent edge probabilities n-a where a ≤ 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 U 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 ⊂ . . . ⊂ FO m ⊂ . . . 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. © Copyright 2008 ACM.

Duke Scholars

Altmetric Attention Stats
Dimensions Citation Stats

Published In

Proceedings of the Annual ACM Symposium on Theory of Computing

DOI

ISSN

0737-8017

ISBN

9781605580470

Publication Date

January 1, 2008

Start / End Page

721 / 730
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Rossman, B. (2008). On the constant-depth complexity of k-clique. In Proceedings of the Annual ACM Symposium on Theory of Computing (pp. 721–730). https://doi.org/10.1145/1374376.1374480
Rossman, B. “On the constant-depth complexity of k-clique.” In Proceedings of the Annual ACM Symposium on Theory of Computing, 721–30, 2008. https://doi.org/10.1145/1374376.1374480.
Rossman B. On the constant-depth complexity of k-clique. In: Proceedings of the Annual ACM Symposium on Theory of Computing. 2008. p. 721–30.
Rossman, B. “On the constant-depth complexity of k-clique.” Proceedings of the Annual ACM Symposium on Theory of Computing, 2008, pp. 721–30. Scopus, doi:10.1145/1374376.1374480.
Rossman B. On the constant-depth complexity of k-clique. Proceedings of the Annual ACM Symposium on Theory of Computing. 2008. p. 721–730.

Published In

Proceedings of the Annual ACM Symposium on Theory of Computing

DOI

ISSN

0737-8017

ISBN

9781605580470

Publication Date

January 1, 2008

Start / End Page

721 / 730