Skip to main content

Formulas versus circuits for small distance connectivity

Publication ,  Conference
Rossman, B
Published in: SIAM Journal on Computing
January 1, 2018

We prove an nΩ (log k) lower bound on the AC0formula size of Distance k(n) Connectivity for all k(n) ≤ log log n and formulas up to depth log n/(log log n)O(1). This lower bound strongly separates the power of bounded-depth formulas versus circuits, since Distance k(n) Connectivity is solvable by polynomial-size AC0circuits of depth O(log k). For all d(n) ≤ log log log n, it follows that polynomial-size depth-d circuits-which are a semantic subclass of nO(d)size depth-d formulas-are not a semantic subclass of no(d)-size formulas of much higher depth log n/(log log n)O(1). Our lower bound technique probabilistically associates each gate in an AC0 formula with an object called a pathset. We show that with high probability these random pathsets satisfy a family of density constraints called smallness, a property akin to low average sensitivity. We then study a complexity measure on small pathsets, which lower bounds the AC0 formula size of Distance k(n) Connectivity. The heart of our technique is an nΩ (log k) lower bound on this pathset complexity measure.

Duke Scholars

Published In

SIAM Journal on Computing

DOI

EISSN

1095-7111

ISSN

0097-5397

Publication Date

January 1, 2018

Volume

47

Issue

5

Start / End Page

1986 / 2028

Related Subject Headings

  • Computation Theory & Mathematics
  • 0802 Computation Theory and Mathematics
  • 0101 Pure Mathematics
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Rossman, B. (2018). Formulas versus circuits for small distance connectivity. In SIAM Journal on Computing (Vol. 47, pp. 1986–2028). https://doi.org/10.1137/15M1027310
Rossman, B. “Formulas versus circuits for small distance connectivity.” In SIAM Journal on Computing, 47:1986–2028, 2018. https://doi.org/10.1137/15M1027310.
Rossman B. Formulas versus circuits for small distance connectivity. In: SIAM Journal on Computing. 2018. p. 1986–2028.
Rossman, B. “Formulas versus circuits for small distance connectivity.” SIAM Journal on Computing, vol. 47, no. 5, 2018, pp. 1986–2028. Scopus, doi:10.1137/15M1027310.
Rossman B. Formulas versus circuits for small distance connectivity. SIAM Journal on Computing. 2018. p. 1986–2028.

Published In

SIAM Journal on Computing

DOI

EISSN

1095-7111

ISSN

0097-5397

Publication Date

January 1, 2018

Volume

47

Issue

5

Start / End Page

1986 / 2028

Related Subject Headings

  • Computation Theory & Mathematics
  • 0802 Computation Theory and Mathematics
  • 0101 Pure Mathematics