Near-optimal small-depth lower bounds for small distance connectivity
- Submitting institution
-
The University of Warwick
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 11934
- Type
- E - Conference contribution
- DOI
-
10.1145/2897518.2897534
- Title of conference / published proceedings
- STOC 2016: 48th Annual Symposium on the Theory of Computing
- First page
- 612
- Volume
- -
- Issue
- -
- ISSN
- -
- Open access status
- -
- Month of publication
- -
- Year of publication
- 2016
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
3
- Research group(s)
-
T - Theory and Foundations
- Citation count
- 8
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- Published in one of the two top theory conferences. Establishes the first near-optimal lower bound on the parallel complexity of the fundamental distance-k connectivity problem. This is the culmination of a sequence of works on this problem by leading researchers in algorithms and complexity: [Ajtai, APAL'89], [Bellantoni, Pitassi, and Urquhart, SICOMP'92], [Beame, Impagliazzo, and Pitassi, CC'98], and [Rossman, STOC'14]. A subsequent article (Srinivasan, EATCS Bulletin "Computational Complexity Column") was dedicated to the main technique employed in this paper and its consequences in circuit complexity, which include "... the resolution of some long standing open problems in the area".
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -