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

Cites work

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

Cited in

(6)

Approximating the geometric knapsack problem in near-linear time and dynamically
Deterministic 3SUM-hardness
Listing 4-cycles
Exploring the approximability landscape of 3SUM
Parameterized algorithms on integer sets with small doubling: integer programming, subset sum and k-SUM
Title not available (Why is no real title available?)

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)