Higher lower bounds from the 3SUM conjecture

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

Authors: Tsvi Kopelowitz, Seth Pettie, Ely Porat 

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (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

Recommendations

• Matching triangles and basing hardness on an extremely popular conjecture
• Towards polynomial lower bounds for dynamic problems
• Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
• Threesomes, degenerates, and love triangles
• 3SUM, 3XOR, triangles

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cited In (33)

• Matching triangles and basing hardness on an extremely popular conjecture
• Dynamic matching: reducing integral algorithms to approximately-maximal fractional algorithms
• Subquadratic algorithms for algebraic 3SUM
• 3SUM, 3XOR, triangles
• Universal Hashing via Integer Arithmetic Without Primes, Revisited
• Capturing points with a rotating polygon (and a 3D extension)
• How fast can we play Tetris greedily with rectangular pieces?
• A comparative study of dictionary matching with gaps: limitations, techniques and challenges
• Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
• Online recognition of dictionary with one gap
• Mind the gap!
• Nearly optimal separation between partially and fully retroactive data structures
• Threesomes, degenerates, and love triangles
• On Multidimensional and Monotone k-SUM
• Simultaneously load balancing for every \(p\)-norm, with reassignments
• The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance
• Ranked document retrieval for multiple patterns
• Deterministic dynamic matching in worst-case update time
• Towards polynomial lower bounds for dynamic problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• \(k\)-SUM in the sparse regime: complexity and applications
• Gapped indexing for consecutive occurrences
• Stronger 3-SUM lower bounds for approximate distance oracles via additive combinatorics
• Conditional hardness for sensitivity problems
• A subquadratic algorithm for 3XOR
• Internal masked prefix sums and its connection to fully internal measurement queries
• Clustered Integer 3SUM via Additive Combinatorics
• Improved bounds for 3SUM, \(k\)-SUM, and linear degeneracy
• Connectivity oracles for graphs subject to vertex failures
• Faster combinatorial \(k\)-clique algorithms
• Dynamic data structures for timed automata acceptance
• How hard is it to find (honest) witnesses?

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)