New Unconditional Hardness Results for Dynamic and Online Problems

Raphael Clifford, Allan Grønlund, Kasper Green Larsen

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

17 Citations (Scopus)
272 Downloads (Pure)

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 languageEnglish
Title of host publication2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS)
Subtitle of host publicationProceedings of a meeting held 17-20 October 2015, Berkeley, California, USA.
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages1089-1107
Number of pages19
Volume56
ISBN (Electronic)9781467381918
ISBN (Print)9781467381925
DOIs
Publication statusPublished - 17 Dec 2015

Publication series

NameAnnual Symposium on Foundations of Computer Science
PublisherIEEE Computer Society Press
Volume56
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.

Cite this