A subquadratic algorithm for 3XOR

DOI10.4230/LIPIcs.MFCS.2018.59OpenAlexW2964138151MaRDI QIDQ5005162

Stefan Walzer, Philipp Schlag, Martin Dietzfelbinger

Publication date: 4 August 2021

Full work available at URL: https://arxiv.org/abs/1804.11086

zbMATH Keywords

reductionsrandomized algorithms3SUM3XORconditional lower time bounds

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items

Front Matter, Table of Contents, Preface, Conference Organization

Uses Software

• PATRICIA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 3SUM, 3XOR, triangles
• Improved subquadratic 3SUM
• The computational complexity of universal hashing
• Surpassing the information theoretic bound with fusion trees
• Improved parallel integer sorting without concurrent writing
• On a class of \(O(n^ 2)\) problems in computational geometry
• Subquadratic algorithms for 3SUM
• Deterministic Dictionaries
• Towards polynomial lower bounds for dynamic problems
• Space-Efficient Randomized Algorithms for K-SUM
• Clustered Integer 3SUM via Additive Combinatorics
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Threesomes, Degenerates, and Love Triangles
• Higher Lower Bounds from the 3SUM Conjecture
• Universal hashing and k-wise independent random variables via integer arithmetic without primes
• Deterministic sorting in O(nloglogn) time and linear space
• Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy
• Near-optimal linear decision trees for k-SUM and related problems
• Algorithms and Data Structures