3SUM Hardness in (Dynamic) Data Structures.
Tsvi Kopelowitz, Seth Pettie, Ely Porat · arXiv (Cornell University) · 2014
We prove lower bounds for several (dynamic) data structure problems conditioned on the well known conjecture that 3SUM cannot be solved in O(n2−Ω(1)) time. This continues a line of work that was initiated by Pǎtraşcu [STOC 2010] and strengthened recently by Abboud and Vassilevska-Williams [FOCS 2014]. The problems we consider are from several subfields of algorithms, including text indexing, dynamic and fault tolerant graph problems, and distance oracles. In particular we prove polynomial lower bounds for the data structure version of the following problems: Dictionary Matching with Gaps, Document Retrieval problems with more than one pattern or an excluded pattern, Maximum Cardinality Matching in bipartite graphs (improving known lower bounds), d-failure Connectivity Oracles, Preprocessing for Induced Subgraphs, and Distance Oracles for Colors. Our lower bounds are based on several reductions from 3SUM to a special set intersection problem introduced by Pǎtraşcu, which we call Pǎtraşcu’s Problem. In particular, we provide a new reduction from 3SUM to Pǎtraşcu’s Problem which allows us to obtain stronger conditional lower bounds for (some) problems that have already been shown to be 3SUM hard, and for several of the problems examined here. Our other lower bounds are based on reductions from the Convolution3SUM problem, which was introduced by Pǎtraşcu. We also prove that up to a logarithmic factor, the Convolution3SUM problem is equivalent to 3SUM when the inputs are integers. A previous reduction of Pǎtraşcu shows that a subquadratic algorithm for Convolu-tion3SUM implies a similarly subquadratic 3SUM algorithm, but not that the two problems are asymptotically equivalent or nearly equivalent. 1