Higher Lower Bounds from the 3SUM Conjecture
Talkat Computational Complexity of Low-Polynomial Time Problems (Simons Institute workshop, 2015) · on Tuesday, 2015-12-08
summary
Shows a direct reduction that reduces 3SUM directly to set disjointness and to reporting set intersection using hashing, giving stronger lower bounds and a weaker 3SUM hypothesis: nontrivial hardness already at exponent 1.5 (previous threshold 13/7). Uses almost-linear, pairwise-independent hashing to bucket and preserve sums, producing N log N sets, total set-size ≈ N^2/R and ≈ N·R queries; choosing R trades preprocessing vs query time. Builds dense graph instances (≈N^{2/3} vertices, N^{4/3} edges) and derives dynamic matching/reporting trade-offs and a quirky amortized exponent (√17−1)/8.
AI-written summary · about
chapters (19)
- 0:00Introduction
- 0:10The Problem
- 1:22Strong 3SUM
- 3:27Hard Distribution
- 4:53Threesome in Geometry
- 6:37Petrovsky
- 8:07Petrovovsky Reductions
- 13:31Set Destroying
- 14:40Mean Hashing
- 16:18Counter Example
- 17:46hashing for Universe Reduction
- 21:28Threesome Witness
- 23:16Intersection Query
- 27:58Online Set Destroying
- 30:35Limitations
- 32:38Set Intersection
- 34:53Tradeoff Curve
- 36:30Dynamic Maximum Matching
- 43:17Open Problem