Math @ Duke

Publications [#348693] of Benjamin Rossman
Papers Published
 Rossman, B, On the constantdepth complexity of kclique,
Proceedings of the Annual Acm Symposium on Theory of Computing
(January, 2008),
pp. 721730, ISBN 9781605580470 [doi]
(last updated on 2022/05/19)
Abstract: We prove a lower bound of ω(nK/4) on the size of constantdepth circuits solving the kclique problem on nvertex 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 sizedepth tradeoff. Our kelique 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 constantdepth circuits of size O(nt). Let G be an ErdösRényi random graph with vertex set {1, . . . , n} and independent edge probabilities na where a ≤ 1/2t1. Let A be a uniform random kelement 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 longstanding open question in finite model theory (going back at least to Immerman in 1982). The mvariable fragment of firstorder logic, denoted by FOm, consists of the firstorder 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 firstorder logic on finite ordered graphs. © Copyright 2008 ACM.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

