The Library
Near-optimal small-depth lower bounds for small distance connectivity
Tools
Chen, Xi, Oliveira, Igor C., Servedio, Rocco A. and Tan, Li-Yang (2016) Near-optimal small-depth lower bounds for small distance connectivity. In: STOC 2016: 48th Annual Symposium on the Theory of Computing, Cambridge, MA, USA, 19-21 Jun 2016. Published in: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing pp. 612-625. ISBN 9781450341325. doi:10.1145/2897518.2897534
|
PDF
WRAP-near-optimal-small-depth-lower-bounds-small-distance-connectivity-Oliveira-2016.pdf - Accepted Version - Requires a PDF viewer. Download (1168Kb) | Preview |
Official URL: http://dx.doi.org/10.1145/2897518.2897534
Abstract
We show that any depth-d circuit for determining whether an n-node graph has an s-to-t path of length at most k must have size nΩ(k1/d/d). The previous best circuit size lower bounds for this problem were nkexp(−O(d)) (due to Beame, Impagliazzo, and Pitassi [BIP98]) and nΩ((log k)/d) (following from a recent formula size lower bound of Rossman [Ros14]). Our lower bound is quite close to optimal, since a simple construction gives depth-d circuits of size nO(k2/d) for this problem (and strengthening our bound even to nkΩ(1/d) would require proving that undirected connectivity is not in NC1.) Our proof is by reduction to a new lower bound on the size of small-depth circuits computing a skewed variant of the “Sipser functions” that have played an important role in classical circuit lower bounds [Sip83, Yao85, H˚as86]. A key ingredient in our proof of the required lower bound for these Sipser-like functions is the use of random projections, an extension of random restrictions which were recently employed in [RST15]. Random projections allow us to obtain sharper quantitative bounds while employing simpler arguments, both conceptually and technically, than in the previous works [Ajt89, BPU92, BIP98, Ros14].
Item Type: | Conference Item (Paper) | |||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | |||||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||||||||
Library of Congress Subject Headings (LCSH): | Computational complexity, Logic, Symbolic and mathematical | |||||||||||||||
Series Name: | STOC: ACM Symposium on Theory of Computing | |||||||||||||||
Journal or Publication Title: | Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | |||||||||||||||
Publisher: | ACM | |||||||||||||||
ISBN: | 9781450341325 | |||||||||||||||
Book Title: | Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing - STOC 2016 | |||||||||||||||
Official Date: | 2016 | |||||||||||||||
Dates: |
|
|||||||||||||||
Page Range: | pp. 612-625 | |||||||||||||||
DOI: | 10.1145/2897518.2897534 | |||||||||||||||
Status: | Peer Reviewed | |||||||||||||||
Publication Status: | Published | |||||||||||||||
Reuse Statement (publisher, data, author rights): | © ACM 2016. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, http://dx.doi.org/10.1145/2897518.2897534. | |||||||||||||||
Access rights to Published version: | Restricted or Subscription Access | |||||||||||||||
Date of first compliant deposit: | 7 November 2019 | |||||||||||||||
Date of first compliant Open Access: | 7 November 2019 | |||||||||||||||
RIOXX Funder/Project Grant: |
|
|||||||||||||||
Conference Paper Type: | Paper | |||||||||||||||
Title of Event: | STOC 2016: 48th Annual Symposium on the Theory of Computing | |||||||||||||||
Type of Event: | Conference | |||||||||||||||
Location of Event: | Cambridge, MA, USA | |||||||||||||||
Date(s) of Event: | 19-21 Jun 2016 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year