Browse/search for people

Publication - Dr Raphael Clifford

    New Unconditional Hardness Results for Dynamic and Online Problems


    Clifford, R, Grønlund, A & Larsen, KG, 2016, ‘New Unconditional Hardness Results for Dynamic and Online Problems’. in: 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS): Proceedings of a meeting held 17-20 October 2015, Berkeley, California, USA. . Institute of Electrical and Electronics Engineers (IEEE), pp. 1089-1107


    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.

    Full details in the University publications repository