New Unconditional Hardness Results for Dynamic and Online Problems
New Unconditional Hardness Results for Dynamic and Online Problems
复制标题
DOI：
10.1109/focs.2015.71
复制
发表时间：
2015-04
期刊：
影响因子：
--
通讯作者：
R. Clifford;A. Jørgensen;Kasper Green Larsen
中科院分区：
文献类型：
--
作者：
R. Clifford;A. Jørgensen;Kasper Green Larsen
有一个复苏的兴趣在下界的真理依赖于已知的计算问题的约束的硬度。由于证明强无条件下界的进展非常缓慢，这些条件下界变得重要和流行。然而，长期目标是用无条件的边界取代这些条件边界。在本文中，我们在这个方向上取得进展，通过研究细胞探针复杂性的两个被证明是硬问题的特别重要的：矩阵向量乘法和一个版本的动态集不相交被称为帕特拉斯库的多相问题。我们改进了这些问题的无条件下界，以及引入新的证明技术的独立利益。其中包括一种能够证明以下形式的强阈值下限的技术：如果我们坚持要有一个非常快的查询时间，那么更新时间必须足够慢，以计算一个查找表，每个可能的查询的答案。这是第一次证明这种类型的下界。
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.