New Unconditional Hardness Results for Dynamic and Online Problems
- Submitting institution
-
University of Bristol
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 95488566
- Type
- E - Conference contribution
- DOI
-
10.1109/FOCS.2015.71
- Title of conference / published proceedings
- 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS) : Proceedings of a meeting held 17-20 October 2015, Berkeley, California, USA.
- First page
- 1089
- Volume
- 56
- Issue
- -
- ISSN
- 0272-5428
- Open access status
- Out of scope for open access requirements
- Month of publication
- December
- Year of publication
- 2015
- 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
-
2
- Research group(s)
-
D - Fundamentals of Computing
- Citation count
- 9
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- At the time of publication, this paper established the strongest unconditional lower bounds for any dynamic data structure problem and introduced new proof techniques into the field. The problems considered are Pătrașcu's Multiphase Problem, otherwise known as dynamic set disjointness, and matrix-vector multiplication. While separation proofs for the main complexity classes, e.g. P vs NP, remain out of reach, lower bounds of this sort give a significant step in establishing the limits of what is computationally possible. The work stands in contrast to the recent trend in computer science of much weaker conditional lower bounds.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -