Higher Lower Bounds from the 3SUM Conjecture

DOI10.1137/1.9781611974331.CH89zbMath1410.68147arXiv1407.6756OpenAlexW2949942995MaRDI QIDQ4575670

Ely Porat, Seth Pettie, Tsvi Kopelowitz

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

Related Items (29)

Matching Triangles and Basing Hardness on an Extremely Popular Conjecture ⋮ Simultaneously load balancing for every p-norm, with reassignments ⋮ Mind the gap! ⋮ Subquadratic algorithms for algebraic 3SUM ⋮ Deterministic dynamic matching in worst-case update time ⋮ Internal masked prefix sums and its connection to fully internal measurement queries ⋮ How fast can we play Tetris greedily with rectangular pieces? ⋮ Universal Hashing via Integer Arithmetic Without Primes, Revisited ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Gapped indexing for consecutive occurrences ⋮ Online recognition of dictionary with one gap ⋮ The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance ⋮ A subquadratic algorithm for 3XOR ⋮ Range closest-pair search in higher dimensions ⋮ Capturing points with a rotating polygon (and a 3D extension) ⋮ Stronger 3-SUM lower bounds for approximate distance oracles via additive combinatorics ⋮ Parameterized aspects of triangle enumeration ⋮ Ranked document retrieval for multiple patterns ⋮ Faster combinatorial \(k\)-clique algorithms ⋮ \(k\)-SUM in the sparse regime: complexity and applications ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Connectivity Oracles for Graphs Subject to Vertex Failures ⋮ On Multidimensional and Monotone k-SUM ⋮ Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy ⋮ Dynamic data structures for timed automata acceptance ⋮ Unnamed Item ⋮ A comparative study of dictionary matching with gaps: limitations, techniques and challenges

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