Stronger 3-SUM lower bounds for approximate distance oracles via additive combinatorics

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 ² ) 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