Removing additive structure in 3SUM-based reductions

Cites work

A complete annotated bibliography of work related to Sidon sequences
A new proof of Szemerédi's theorem
A shortest cycle for each vertex of a graph
A statistical theorem of set addition
A subquadratic approximation scheme for partition
Additive combinatorics
All non-trivial variants of 3-LDT are equivalent
Approximate distance oracles
Approximate distance oracles with constant query time
Automata, Languages and Programming
Clustered Integer 3SUM via Additive Combinatorics
Color-coding
Dynamic low-stretch trees via dynamic low-diameter decompositions
Enumeration complexity of conjunctive queries with functional dependencies
Enumeration complexity of conjunctive queries with functional dependencies
Essentially optimal sparse polynomial multiplication
Faster Space-Efficient Algorithms for Subset Sum, $k$-Sum, and Related Problems
Finding and counting given length cycles
Finding Even Cycles Even Faster
Finding even cycles faster via capped k-walks
Finding, minimizing, and counting weighted subgraphs
Fine-grained complexity for sparse graphs
Graph Theory and Additive Combinatorics
scientific article; zbMATH DE number 5663738 (Why is no real title available?)
Improved distance queries and cycle counting by Frobenius normal form
Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication
Nearly Optimal Sparse Polynomial Multiplication
On a Problem of Sidon in Additive Number Theory, and on some Related Problems
On closest pair in Euclidean metric: monochromatic is as hard as bichromatic
On hardness of jumbled indexing
On Multidimensional and Monotone k-SUM
On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
On some fine-grained questions in algorithms and complexity
On the difference between closest, furthest, and orthogonal pairs: nearly-linear vs barely-subquadratic complexity
Output-sensitive algorithms for sumset and sparse polynomial multiplication
Settling SETH vs. approximate sparse directed unweighted diameter (up to (NU)NSETH)
Sparse nonnegative convolution is equivalent to dense nonnegative convolution
Subquadratic algorithms for 3SUM
Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems
Tight conditional lower bounds for approximating diameter in directed graphs
Tight hardness for shortest cycles and paths in sparse graphs
Top-𝑘-convolution and the quest for near-linear output-sensitive subset sum
Towards polynomial lower bounds for dynamic problems
Universal hashing and $k$-wise independent random variables via integer arithmetic without primes
Universal Hashing via Integer Arithmetic Without Primes, Revisited
Verifying candidate matches in sparse and wildcard matching
What can (and can't) we do with sparse polynomials?

Cited in

(6)

Join sampling under acyclic degree constraints and (cyclic) subgraph sampling
Deterministic 3SUM-hardness
Join and subgraph sampling under degree constraints
Listing 4-cycles
Exploring the approximability landscape of 3SUM
Parameterized algorithms on integer sets with small doubling: integer programming, subset sum and k-SUM

This page was built for publication: Removing additive structure in 3SUM-based reductions

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