Near-optimal small-depth lower bounds for small distance connectivity

DOI10.1145/2897518.2897534zbMath1373.68260arXiv1509.07476OpenAlexW1913417089MaRDI QIDQ5361865

Igor C. Oliveira, Li-Yang Tan, Xi Chen, Rocco A. Servedio

Publication date: 29 September 2017

Published in: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1509.07476

zbMATH Keywords

connectivityrandom projectionssmall-depth circuitsswitching lemma

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Connectivity (05C40)

Related Items (7)

Formulas versus Circuits for Small Distance Connectivity ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Parity helps to compute majority ⋮ Prediction from partial information and hindsight, with application to circuit lower bounds ⋮ Unnamed Item ⋮ Dynamic complexity of expansion

This page was built for publication: Near-optimal small-depth lower bounds for small distance connectivity