Abstract: We show that if one can solve 3SUM on a set of size n in time n^{1+e} then one can list t triangles in a graph with m edges in time O(m^{1+e}t^{1/3-e/3}). This is a reversal of Patrascu's reduction from 3SUM to listing triangles (STOC '10). Our result builds on and extends works by the Paghs (PODS '06) and by Vassilevska and Williams (FOCS '10). We make our reductions deterministic using tools from pseudorandomness. We then re-execute both Patrascu's reduction and our reversal for the variant 3XOR of 3SUM where integer summation is replaced by bit-wise xor. As a corollary we obtain that if 3XOR is solvable in linear time but 3SUM requires quadratic randomized time, or vice versa, then the randomized time complexity of listing m triangles in a graph with edges is m^{4/3} up to a factor m^alpha for any alpha > 0.
Recommendations
Cites work
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Finding and counting given length cycles
- Finding, minimizing, and counting weighted subgraphs
- Hardness vs randomness
- scientific article; zbMATH DE number 1351079 (Why is no real title available?)
- scientific article; zbMATH DE number 1004938 (Why is no real title available?)
- Introduction to algorithms
- Listing triangles
- Lower bounds for linear degeneracy testing
- On a class of \(O(n^ 2)\) problems in computational geometry
- On the possibility of faster \textsc{SAT} algorithms
- Sets of integers that do not contain long arithmetic progressions
- Simple Constructions of Almost k-wise Independent Random Variables
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- Subquadratic algorithms for 3SUM
- The intractability of computing the minimum distance of a code
- Threesomes, degenerates, and love triangles
- Towards polynomial lower bounds for dynamic problems
- Universal hashing and \(k\)-wise independent random variables via integer arithmetic without primes
- Which problems have strongly exponential complexity?
Cited in
(14)- Geometric pattern matching reduces to \(k\)-SUM
- Threesomes, degenerates, and love triangles
- Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
- Higher lower bounds from the 3SUM conjecture
- A subquadratic algorithm for 3XOR
- On nondeterministic derandomization of Freivalds' algorithm: consequences, avenues and algorithmic progress
- On Multidimensional and Monotone k-SUM
- Exact weight subgraphs and the k-sum conjecture
- Improved Merlin-Arthur protocols for central problems in fine-grained complexity
- Towards optimal set-disjointness and set-intersection data structures
- On the fine-grained complexity of parity problems
- Fine-grained complexity in a world without cryptography
- A k-swap local search for makespan scheduling
- Fine-grained cryptanalysis: tight conditional bounds for dense \(k\)-SUM and \(k\)-XOR
This page was built for publication: 3SUM, 3XOR, triangles
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q261365)
