3SUM, 3XOR, triangles
From MaRDI portal
Publication:261365
DOI10.1007/s00453-014-9946-9zbMath1336.68132arXiv1305.3827OpenAlexW2963340918MaRDI QIDQ261365
Emanuele Viola, Zahra Jafargholi
Publication date: 23 March 2016
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1305.3827
Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)
Related Items (7)
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture ⋮ Exact Weight Subgraphs and the k-Sum Conjecture ⋮ Geometric pattern matching reduces to \(k\)-SUM ⋮ Improved Merlin-Arthur protocols for central problems in fine-grained complexity ⋮ Unnamed Item ⋮ A subquadratic algorithm for 3XOR ⋮ On Multidimensional and Monotone k-SUM
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Sets of integers that do not contain long arithmetic progressions
- Finding and counting given length cycles
- Hardness vs randomness
- Which problems have strongly exponential complexity?
- An improved construction of progression-free sets
- On a class of \(O(n^ 2)\) problems in computational geometry
- Subquadratic algorithms for 3SUM
- Towards polynomial lower bounds for dynamic problems
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- Simple Constructions of Almost k-wise Independent Random Variables
- The intractability of computing the minimum distance of a code
- Threesomes, Degenerates, and Love Triangles
- Universal hashing and k-wise independent random variables via integer arithmetic without primes
- Listing Triangles
- Finding, minimizing, and counting weighted subgraphs
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Lower bounds for linear degeneracy testing
This page was built for publication: 3SUM, 3XOR, triangles
