Stronger 3-SUM lower bounds for approximate distance oracles via additive combinatorics
From MaRDI portal
Publication:6499237
DOI10.1145/3564246.3585240MaRDI QIDQ6499237
Nick Fischer, Karl Bringmann, Amir Abboud
Publication date: 8 May 2024
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finding and counting given length cycles
- Ramsey partitions and proximity data structures
- All-pairs nearly 2-approximate shortest paths in \(O(n^2 \text{ polylog } n)\) time
- On Lipschitz embedding of finite metric spaces in Hilbert space
- A statistical theorem of set addition
- On a class of \(O(n^ 2)\) problems in computational geometry
- On the distortion required for embedding finite metric spaces into normed spaces
- Subquadratic algorithms for 3SUM
- On a question of Erdős and Moser
- All-Pairs Small-Stretch Paths
- Output-Sensitive Algorithms for Sumset and Sparse Polynomial Multiplication
- Towards polynomial lower bounds for dynamic problems
- Losing Weight by Gaining Edges
- Approximate Distance Oracles with Improved Bounds
- Clustered Integer 3SUM via Additive Combinatorics
- Approximate distance oracles for unweighted graphs in expected O ( n 2 ) time
- Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
- Approximate distance oracles
- Verifying candidate matches in sparse and wildcard matching
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
- Near-Linear Time Construction of Sparse Neighborhood Covers
- Finding Even Cycles Even Faster
- Higher Lower Bounds from the 3SUM Conjecture
- All-Pairs Approximate Shortest Paths and Distance Oracle Preprocessing
- Linear Hashing Is Awesome
- $(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
- All-Pairs Almost Shortest Paths
- Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication
- Nearly Optimal Sparse Polynomial Multiplication
- An almost 2-approximation for all-pairs of shortest paths in subquadratic time
- New (α, β) Spanners and Hopsets
- Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler
- Listing Triangles
- Bypassing Erdős’ Girth Conjecture: Hybrid Stretch and Sourcewise Spanners
- Distance Oracles for Sparse Graphs
- Almost optimal distance oracles for planar graphs
- Approximate distance oracles with constant query time
- Faster Algorithms for All-pairs Approximate Shortest Paths in Undirected Graphs
- Distance Oracles beyond the Thorup--Zwick Bound
- Eine zahlentheoretische Anwendung der Graphentheorie.
- Approximate Distance Oracles with Improved Query Time
- Optimal Listing of Cycles and st-Paths in Undirected Graphs
- A new proof of Szemerédi's theorem
- Approximate distance oracles with improved stretch for sparse graphs
- Sparse nonnegative convolution is equivalent to dense nonnegative convolution
This page was built for publication: Stronger 3-SUM lower bounds for approximate distance oracles via additive combinatorics