Deterministic 3SUM-Hardness

1.1 Our Results

• The toolkit combines a deterministic additive hash with few collisions and a refined deterministic self-reduction for 3SUM.The authors describe these as simple algorithms tailored to 3SUM rather than heavy black-box derandomization machinery.Source: §1.1 · pp. 3–4
• The toolkit derandomizes almost all known 3SUM-based reductions, while three recent structure-versus-randomness reductions remain randomized.The remaining cases rely on short-cycle removal, with derandomizing algorithmic BSG and specialized additive hashing identified as challenges.Source: §1.1 · p. 4, §1.2 · p. 8
• If 3SUM over [n^3] has a deterministic O(n^(2−ε))-time algorithm, then 3SUM over [U] has one in O(n^(2−ε′) log^c U) time.The reduction is a fine-grained reduction from large-universe 3SUM to small-universe 3SUM, not a preprocessing step; its log U factor does not replace U-dependence with n-dependence.Source: §1.1 · p. 4
• Theorems 1.4 and 1.6 establish deterministic hardness for offline Set Disjointness and Set Intersection under the deterministic 3SUM hypothesis.The Set Intersection theorem covers parameter ranges in which the total number of listed elements is O(n^(2−β)).Source: §1.1 · pp. 4–5

1.2 The Landscape of 3SUM-Based Reductions

• Figure 1 distinguishes previously deterministic regions, regions derandomized here, and a dark-blue region that remains randomized.The figure uses solid arrows for deterministic reductions and dotted arrows for randomized reductions.Source: §1.2 · p. 5, Figure 1 · p. 6
• The Set Disjointness and Set Intersection results derandomize downstream reductions to Triangle Listing and its associated database and range-query problems.The landscape also includes deterministic reductions from Set Intersection to Triangle Listing and from Set Disjointness to All-Edges Triangle.Source: §1.1 · p. 5, §1.2 · p. 7
• The deterministic universe reduction also derandomizes reductions relying on small universes, while tailored arguments address Monochromatic Convolution and Local Alignment.The paper additionally extends universe reductions to cover Dynamic k-Mismatch and Odd Abelian Square.Source: §1.2 · p. 7

1.3 Outline

• The paper outlines preliminaries, the derandomization toolkit, the universe reduction, and deterministic Set Disjointness and Set Intersection hardness results.The full version also presents derandomizations for Monochromatic Convolution, Local Alignment, and Convolution Witness.Source: §1.3 · p. 8

2 Preliminaries

• 3SUM asks whether a set A contains a triple a, b, c with a + b = c.The input set is drawn from universe [U].Source: §2 · p. 8
• All-Numbers 3SUM asks, for each c in A, whether two elements a, b in A sum to c.Source: §2 · p. 8
• Convolution 3SUM asks, for each index k, whether indices i, j satisfy i + j = k and X[i] + X[j] = X[k].Source: §2 · p. 8
• The stated single-set versions are equivalent to three-set versions by deterministic reductions.The paper occasionally relies on this equivalence in its proofs.Source: §2 · p. 8

3.1 Tool 1: Deterministic Additive Hashing

• The hashing recipe builds h(x)=x mod m with m a product of small primes, fixing each prime by conditional expectations and exhaustive local testing.The approach applies to properties that can be tested efficiently.Source: §3.1 · p. 9
• The earlier few-collision lemma deterministically finds m in [n^µ, 2n^µ) in O(n^1+δ) time.Source: §3.1 · p. 9
• For many reductions, few hash collisions are insufficient because modular false positives are the relevant quantity and are hard to count directly.The reduced instance has universe size m, so its 3SUM solutions can be counted using FFT in eO(m) time.Source: §3.1 · p. 9
• Lemma 3.2 gives a deterministic algorithm for O(n)-size 3SUM instances that finds a modulus in [n^µ, 2n^µ) or detects a yes-instance, in eO(g n^max(µ,1)+δ) time.Source: §3.1 · pp. 9–10

3.2 Tool 2: Deterministic Self-Reduction

• The self-reduction partitions A into g sets of size O(n/g) and interval length O(U/g), while O(g^2) tracked triples cover every original 3SUM solution.The construction runs in eO(n+g^2) time.Source: §3.2 · p. 10

3.3 Proofs

• The hashing proof iteratively selects small primes minimizing modular pseudo-solutions, using FFT counts; its running time is eO(g n^max(1,µ)+δ).The modulus grows by at least n^δ per iteration, and the prime-selection computations dominate the running time.Source: §3.3 · pp. 10–11
• When the computed modulus has unexpectedly many pseudo-solutions, the algorithm infers that an input is a yes-instance; it also ensures m lies in [n^µ, 2n^µ).Source: §3.3 · p. 12
• The deterministic self-reductions yield O(g^2) smaller instances for both 3SUM and All-Numbers 3SUM, with eO(ng) reduction time.Each instance has size O(n/g) and universe [O(U/g)].Source: §3.3 · p. 13

4 Deterministic Universe Reduction for 3SUM

• A deterministic O(n2−ε) algorithm for 3SUM over [n^3] would yield an O(n2−ε′ log^c U) algorithm over [U], for constants ε′, c > 0.Consequently, 3SUM over [n^3] has no deterministic O(n2−ε) algorithm unless the deterministic 3SUM hypothesis fails.Source: §4 · pp. 13–14
• The reduction bounds modular pseudo-solutions, searches for them using smaller subinstances, then checks whether any candidate is a genuine 3SUM solution.The pseudo-solutions have 1-to-O(1) correspondence with solutions, and their count is bounded by S.Source: §4 · pp. 13–14

4.1 Universe Reduction for All-Numbers 3SUM

• For any ε > 0, All-Numbers 3SUM over a universe of size n^2 cannot be solved in deterministic time O(n^(2−ε)), unless the deterministic 3SUM hypothesis fails.Source: §4.1 · p. 15

4.2 Universe Reduction for Convolution 3SUM

• Convolution 3SUM over a universe of size n^2 has no deterministic O(n2−ε) algorithm unless the deterministic 3SUM hypothesis fails.The proof follows, starting instead from the paper’s deterministic universe reduction for 3SUM.Source: §4.2 · p. 16

4.3 Universe Reduction for 3SUM Listing

• For 1 < µ < 2, instances over [n^µ] with O(n3−µ) solutions cannot be listed deterministically in O(n2−ε) time unless the deterministic 3SUM hypothesis fails.The reduction adds n1+δ dummy elements so the constructed listing instance has the required size and solution-count bounds.Source: §4.3 · p. 17

Set Disjointness

• For |U|=O(n2−2α), N=O(n), s=O(n1−α), and q=O(n1+α), deterministic Set Disjointness cannot run in O(n2−ε) unless the deterministic 3SUM hypothesis fails.The theorem applies for 0 ≤ α < 1 and any ε > 0.Source: §5 · p. 18
• The Set Disjointness reduction encodes modular 3SUM pseudo-solutions as queried intersections and lists enough intersection elements to recover all candidates.It lists up to threshold t per query, then scans intersections that reach that threshold.Source: §5 · pp. 19–20

Set Intersection

• For 0 ≤ α < 1 and 0 ≤ β ≤ 1−α, deterministic Set Intersection cannot run in O(n2−ε) with the stated parameters and output bound unless the deterministic 3SUM hypothesis fails.The parameters include |U|=O(n1+β−α), N=O(n^2), s=O(n1−α), q=O(n1+α), and up to O(n2−β) listed elements.Source: §5 · p. 21

A Deterministic Lower Bound for Mono Convolution

• Unless the deterministic 3SUM hypothesis fails, Mono Convolution has no deterministic O(n2−ε)-time algorithm for any ε > 0.The reduction turns a faster Mono Convolution algorithm into a subquadratic algorithm for 3SUM.Source: A Deterministic Lower Bound for Mono… · p. 28
• The reduction applies universe reduction and self-reduction, then uses deterministic load balancing to combine smaller 3SUM instances into Mono Convolution instances.The load-balancing lemma partitions the input sets and chooses shifts with bounded overlap properties.Source: A Deterministic Lower Bound for Mono… · p. 28
• Solving O(n15δ) Mono Convolution instances takes O(n2−ε+15δ) time under the assumed O(n3/2−ε)-time algorithm.The parameters can be chosen so the overall reduction runs in truly subquadratic time.Source: A Deterministic Lower Bound for Mono… · p. 29

Deterministic Load Balancing

• The construction selects shifts one at a time by conditional expectations, choosing each to minimize the stated overlap measure.The slow version finds each minimizer using a convolution computed by the Fast Fourier Transform in near-linear time eO(U).Source: §A.1 · pp. 30, 32
• Grouping the input sets and applying the slower lemma to the buckets yields the faster deterministic running time eO(NS + N1−δU).The proof bounds the bucket sizes and transfers their overlap bounds to the original sets.Source: §A.1 · p. 32

• Unless the deterministic 3SUM hypothesis fails, Local Alignment on length-n strings over an alphabet of size eO(n^(1−δ)) has no deterministic O(n^(2−δ−ε))-time algorithm for any ε > 0.Source: B Deterministic Lower Bound for Local… · p. 32
• The reduction follows Abboud, Vassilevska Williams and Weimann, replacing randomized hashing with deterministic few-collisions hashing [CL15].It does not need to control the number of pseudo-solutions.Source: B Deterministic Lower Bound for Local… · p. 33
• For U=n^3, N deterministic maps from [−U,U] to [−⌈log U⌉,⌈log U⌉]^d, with d=O(log U/log log U) and each computable in U^o(1) time, preserve whether a+b+c=0 as a coordinate-wise zero sum under some map.Source: B Deterministic Lower Bound for Local… · p. 33
• The reduction's instance construction and scoring-table costs, together with brute force on heavy buckets, yield a truly subquadratic 3SUM algorithm if the stated Local Alignment running-time bound is met.Source: B Deterministic Lower Bound for Local… · pp. 33–34
• For each map and bucket position, a Local Alignment instance tests bucket-position and coordinate-sum conditions; some instance detects every 3SUM solution.The scoring function rewards coordinate matches when the mapped value for c is the negative sum of the mapped values for a and b.Source: B Deterministic Lower Bound for Local… · pp. 33–34
• The construction is correct because a perfect match has value d exactly when the mapped coordinates satisfy the required sum conditions.Source: B Deterministic Lower Bound for Local… · p. 34

• Convolution Witness preprocesses two binary vectors so a query index returns all witness pairs whose indices sum to that index and whose entries are both 1.Source: C Deterministic Lower Bound for… · p. 34
• Unless the deterministic 3SUM hypothesis fails, Convolution Witness cannot have preprocessing time O(n^(2−α)) and query time O(n^(α/2−ε)) per witness, for any ε > 0.Source: C Deterministic Lower Bound for… · p. 34
• Two deterministic additive hashes produce moduli m1 = Θ(n) and m2 = Θ(n^(α/2−δ)), bounding the pseudo-solutions modulo their product by eO(n^(2−α/2+δ)).Source: C Deterministic Lower Bound for… · p. 35
• The reduction builds vector pairs for residue classes, queries witnesses for the relevant residues, then tests candidate pairs for a 3SUM solution.Source: C Deterministic Lower Bound for… · p. 35
• It enumerates exactly the triples satisfying both modular conditions, so every proper 3SUM solution is found and every reported solution is valid.Source: C Deterministic Lower Bound for… · p. 35
• The hashing, preprocessing, and query costs combine to give a truly subquadratic 3SUM algorithm under the assumed Convolution Witness bounds, contradicting the deterministic 3SUM hypothesis.Source: C Deterministic Lower Bound for… · p. 35