BAD'16 Poster

Bristol Algorithms Days 2016
Workshop on Efficient Algorithms and Lower Bounds

2 - 3 February 2016

  •    •    •  

Unconditional Hardness Results for Dynamic and Online Problems

Allan Grønlund

There has been a resurgence of interest in lower bounds whose truth rests on the conjectured hardness of well known computaktional 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 talk we adress recent progress and present new results on 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 Pătraşcu’s Multiphase Problem.

We present a technique capable of proving a new kind og 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.

Joint Work with Raphael Clifford and Kasper Green Larsen. Our paper can be found here.


  The University of Bristol   EPSRC