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

Cites Work

Additive combinatorics
On a class of $O(n^ 2)$ problems in computational geometry
Subquadratic algorithms for 3SUM
Towards polynomial lower bounds for dynamic problems
Approximate distance oracles
All-Pairs Almost Shortest Paths
Listing triangles
A new proof of Szemerédi's theorem
Finding and counting given length cycles
Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
Near-Linear Time Construction of Sparse Neighborhood Covers
Approximate distance oracles with constant query time
Ramsey partitions and proximity data structures
Distance Oracles for Sparse Graphs
Distance oracles beyond the Thorup-Zwick bound
Approximate distance oracles with improved preprocessing time
Clustered Integer 3SUM via Additive Combinatorics
Verifying candidate matches in sparse and wildcard matching
On Lipschitz embedding of finite metric spaces in Hilbert space
On a question of Erdős and Moser
A statistical theorem of set addition
Title not available (Why is that?)
Eine zahlentheoretische Anwendung der Graphentheorie.
All-pairs nearly 2-approximate shortest paths in $O(n^2 \text{ polylog } n)$ time
All-pairs small-stretch paths
Approximate distance oracles with improved query time
On the distortion required for embedding finite metric spaces into normed spaces
Nearly Optimal Sparse Polynomial Multiplication
Approximate distance oracles for unweighted graphs in expected O ( n ² ) time
Finding Even Cycles Even Faster
Output-sensitive algorithms for sumset and sparse polynomial multiplication
Almost optimal distance oracles for planar graphs
$(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
An almost 2-approximation for all-pairs of shortest paths in subquadratic time
Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler
Optimal listing of cycles and $st$-paths in undirected graphs
Bypassing Erdős' girth conjecture: hybrid stretch and sourcewise spanners
Faster algorithms for all-pairs approximate shortest paths in undirected graphs
Many additive quadruples
Approximate distance oracles with improved bounds
Higher lower bounds from the 3SUM conjecture
Additive spanners and distance oracles in quadratic time
New (α, β) Spanners and Hopsets
Losing weight by gaining edges
Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication
Linear Hashing Is Awesome
All-Pairs Approximate Shortest Paths and Distance Oracle Preprocessing
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

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