  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.
