Higher Lower Bounds from the 3SUM Conjecture

DOI10.1137/1.9781611974331.CH89zbMATH Open1410.68147arXiv1407.6756OpenAlexW2949942995MaRDI QIDQ4575670

Author name not available (Why is that?)

Publication date: 16 July 2018

Published in: (Search for Journal in Brave)

Abstract: The 3SUM conjecture has proven to be a valuable tool for proving conditional lower bounds on dynamic data structures and graph problems. This line of work was initiated by Pv{a}trac{s}cu (STOC 2010) who reduced 3SUM to an offline SetDisjointness problem. However, the reduction introduced by Pv{a}trac{s}cu suffers from several inefficiencies, making it difficult to obtain tight conditional lower bounds from the 3SUM conjecture. In this paper we address many of the deficiencies of Pv{a}trac{s}cu's framework. We give new and efficient reductions from 3SUM to offline SetDisjointness and offline SetIntersection (the reporting version of SetDisjointness) which leads to polynomially higher lower bounds on several problems. Using our reductions, we are able to show the essential optimality of several algorithms, assuming the 3SUM conjecture. - Chiba and Nishizeki's $O(malpha)$-time algorithm (SICOMP 1985) for enumerating all triangles in a graph with arboricity/degeneracy $alpha$ is essentially optimal, for any $alpha$. - Bj{o}rklund, Pagh, Williams, and Zwick's algorithm (ICALP 2014) for listing $t$ triangles is essentially optimal (assuming the matrix multiplication exponent is $omega=2$). - Any static data structure for SetDisjointness that answers queries in constant time must spend $Omega(N^{2-o(1)})$ time in preprocessing, where $N$ is the size of the set system. These statements were unattainable via Pv{a}trac{s}cu's reductions. We also introduce several new reductions from 3SUM to pattern matching problems and dynamic graph problems. Of particular interest are new conditional lower bounds for dynamic versions of Maximum Cardinality Matching, which introduce a new technique for obtaining amortized lower bounds.

Full work available at URL: https://arxiv.org/abs/1407.6756

Mathematics Subject Classification ID

No records found.

This page was built for publication: Higher Lower Bounds from the 3SUM Conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575670)