Projects per year
Abstract
There has been a resurgence of interest in lower bounds whose truth rests on the conjectured hardness of well known computational problems. These conditional lower bounds have become important and popular due to the painfully slow progress on proving strong unconditional lower bounds. Nevertheless, the long term goal is to replace these conditional bounds with unconditional ones. In this paper we make progress in this direction by studying the cell probe complexity of two conjectured to be hard problems of particular importance: matrix-vector multiplication and a version of dynamic set disjointness known as Patrascu's Multiphase Problem. We give improved unconditional lower bounds for these problems as well as introducing new proof techniques of independent interest. These include a technique capable of proving strong threshold lower bounds of the following form: If we insist on having a very fast query time, then the update time has to be slow enough to compute a lookup table with the answer to every possible query. This is the first time a lower bound of this type has been proven.
Original language | English |
---|---|
Title of host publication | 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS) |
Subtitle of host publication | Proceedings of a meeting held 17-20 October 2015, Berkeley, California, USA. |
Publisher | Institute of Electrical and Electronics Engineers (IEEE) |
Pages | 1089-1107 |
Number of pages | 19 |
Volume | 56 |
ISBN (Electronic) | 9781467381918 |
ISBN (Print) | 9781467381925 |
DOIs | |
Publication status | Published - 17 Dec 2015 |
Publication series
Name | Annual Symposium on Foundations of Computer Science |
---|---|
Publisher | IEEE Computer Society Press |
Volume | 56 |
ISSN (Print) | 0272-5428 |
Keywords
- cell-probe model
- computational complexity
- lower bounds
Fingerprint
Dive into the research topics of 'New Unconditional Hardness Results for Dynamic and Online Problems'. Together they form a unique fingerprint.Projects
- 1 Finished
-
Next generation pattern matching
Clifford, R. (Principal Investigator)
1/01/13 → 14/01/19
Project: Research
Profiles
-
Dr Raphael Clifford
- School of Computer Science - Reader in Algorithm Design
- Intelligent Systems Laboratory
- Algorithms and Complexity
Person: Academic , Member, Group lead