Clustered Integer 3SUM via Additive Combinatorics
Talkat Computational Complexity of Low-Polynomial Time Problems (Simons Institute workshop, 2015) · on Tuesday, 2015-12-08
summary
Claims a preprocessing scheme that uses Balog-Szemerédi-Gowers structure to cover A0,B0,S0 in randomized O~(n^2) preprocessing and answer subset three-sum queries in about n^{13/7} (~n^{1.857}) time by iteratively peeling dense sum-pairs, constructing A′,B′ blocks, and handling leftovers. Tools: additive combinatorics + a constructive randomized BSG routine, sparse FFT / pseudo-additive hashing to enumerate tight sum-sets. Extensions give deterministic ~n^{1.864} and specialized bounded-monotone min-plus convolution algorithms with similar exponents; the construction and timing are implemented and analyzed.
AI-written summary · about
chapters (18)
- 0:00Intro
- 0:54SumSet problems
- 6:20Additive Combinatorics
- 7:083SUM in Preprocessed World
- 9:33Balog-Szemeredi-Gowers
- 13:17How to use BSG Theorem
- 19:05FFT Lemma
- 20:06Special cases of 3SUM and APSP
- 21:37Open Special Cases
- 23:42New Results
- 24:03Bounded Int. Montone Min+Conv
- 24:27Simplification
- 24:57Monotone (min,+)-convolution
- 27:50Compute Upper Envelope of A+B
- 28:04Monotone (min, +)-convolution
- 32:32The Algorithm...
- 37:35Running Time
- 38:01Other Applications