PaperlayerView exact revision on arXiv

Source-linked AI summary

New Applications of 3SUM-Counting in Fine-Grained Complexity and Pattern Matching

Nick Fischer, Ce Jin, Yinzhan Xu

arXiv:2410.20764v1cs.DS

TL;DR

This paper develops deterministic 3SUM-oriented tools to address gaps in derandomizing fine-grained reductions and to improve pattern-matching algorithms. It applies these tools to 4-Cycle Listing hardness, #3SUM equivalence, and pattern-matching results.

  • Problem

    The paper addresses the need for deterministic fine-grained reductions and new 3SUM-based tools for lower bounds and algorithmic applications.

    Source: §1.1 · p. 3, §1 · p. 3

  • Method

    The authors develop deterministic algorithms for 3SUM-type problems and the constructive BSG theorem, then apply these tools to fine-grained complexity and pattern matching.

    Source: §1 · p. 3, §1.1 · p. 4

  • Results

    The paper establishes deterministic 4-Cycle Listing lower bounds and deterministic fine-grained equivalence between 3SUM and #3SUM, alongside faster deterministic pattern-matching algorithms.

    Source: §1.1 · p. 4, §1.2 · p. 5

  • Takeaways & Limitations

    The results show that 3SUM-oriented tools can support both new fine-grained lower bounds and faster pattern-matching algorithms.

    Source: §1 · p. 3

    The deterministic reduction does not immediately establish conditional lower bounds for Distance Oracles, and derandomizing that reduction remains open.

    Source: §1.4 · p. 11

Abstract

from arXiv · show

The 3SUM problem is one of the cornerstones of fine-grained complexity. Its study has led to countless lower bounds, but as has been sporadically observed before -- and as we will demonstrate again -- insights on 3SUM can also lead to algorithmic applications. The starting point of our work is that we spend a lot of technical effort to develop new algorithms for 3SUM-type problems such as approximate 3SUM-counting, small-doubling 3SUM-counting, and a deterministic subquadratic-time algorithm for the celebrated Balog-Szemer\'edi-Gowers theorem from additive combinatorics. As consequences of these tools, we derive diverse new results in fine-grained complexity and pattern matching algorithms, answering open questions from many unrelated research areas. Specifically: - A recent line of research on the "short cycle removal" technique culminated in tight 3SUM-based lower bounds for various graph problems via randomized fine-grained reductions [Abboud, Bringmann, Fischer; STOC '23] [Jin, Xu; STOC '23]. In this paper we derandomize the reduction to the important 4-Cycle Listing problem. - We establish that \#3SUM and 3SUM are fine-grained equivalent under deterministic reductions. - We give a deterministic algorithm for the $(1+\epsilon)$-approximate Text-to-Pattern Hamming Distances problem in time $n^{1+o(1)} \cdot \epsilon^{-1}$. - In the $k$-Mismatch Constellation problem the input consists of two integer sets $A, B \subseteq [N]$, and the goal is to test whether there is a shift $c$ such that $|(c + B) \setminus A| \leq k$ (i.e., whether $B$ shifted by $c$ matches $A$ up to $k$ mismatches). For moderately small $k$ the previously best running time was $\tilde O(|A| \cdot k)$ [Cardoze, Schulman; FOCS '98] [Fischer; SODA '24]. We give a faster $|A| \cdot k^{2/3} \cdot N^{o(1)}$-time algorithm in the regime where $|B| = \Theta(|A|)$.

1 Introduction

The paper develops deterministic 3SUM-related tools, including constructive BSG and popular-sum 3SUM-counting, and applies them to fine-grained complexity and pattern matching. The applications include deterministic 4-Cycle Listing hardness, deterministic 3SUM/#3SUM equivalence, and a faster algorithm for k-Mismatch Constellation, alongside discussion of derandomization limits and open questions.

1 Introduction

  • The paper extends the observed connection between 3SUM fine-grained techniques and pattern matching by developing deterministic 3SUM tools, often using additive combinatorics, for new lower bounds and faster algorithms.The introduction frames this as a further exploration of how techniques developed around 3SUM can yield algorithms for seemingly unrelated problems.Source: §1 · p. 3

1.1 Application 1: Deterministic 3SUM-hardness

  • Under the deterministic 3SUM hypothesis, 4-Cycle Listing has no deterministic O(n^(2−δ)+t) or O(m^(4/3−δ)+t) algorithm for any δ>0.The reduction first maps general 3SUM to instances with additive energy at most n^(2+δ), using a deterministic subquadratic constructive BSG algorithm; the resulting bounds match known upper bounds.Source: §1.1 · p. 4
  • 3SUM and #3SUM are subquadratically equivalent under deterministic reductions.The reduction uses FFT rather than fast matrix multiplication.Source: §1.1 · p. 4

1.2 Application 2: Pattern matching algorithms

  • A deterministic algorithm computes (1+epsilon)-approximations to Text-to-Pattern Hamming Distances in n^(1+o(1))/epsilon time.This improves the deterministic dependence on epsilon from epsilon^-2 to epsilon^-1, with an extra m^o(1) factor.Source: §1.2 · p. 5
  • For 1 ≤ k ≤ 0.3|B|, deterministic k-Mismatch Constellation takes |A|·k^(2/3)·(|A|/|B|)^(2/3)·N^o(1) time.When |B| = Θ(|A|), the running time is |A|·k^(2/3)·N^o(1); under the BMM hypothesis, combinatorial algorithms cannot achieve the near-linear-time goal irrespective of k, and a k^(1/6) gap remains.Source: §1.2 · p. 6
  • For pattern-only wildcards, deterministic k-Mismatch String Matching takes k^(1/2)n^(1+o(1)) time.A reduction from k-Mismatch Constellation also gives a k^(2/3)n^(1+o(1))-time algorithm; the faster bound follows by adjusting parameters and simplifying the proof.Source: §1.2 · pp. 6–7

1.3 Technical tools and overview

  • The technical toolkit includes deterministic approximate popular-sums convolution, exact small-doubling 3SUM counting, and constrained almost-additive hashing.Popular-sums approximation runs in (epsilon^-1|A|+|B|)·N^o(1) time with error at most epsilon|B|; small-doubling counting runs in O(Kn^1.5N^o(1)) when all three sets have size at most n. The hashing construction uses epsilon-biased sets to address the need for approximate 3-wise independence.Source: §1.3 · pp. 7–9
  • Theorem 1.11 gives a deterministic subquadratic-time constructive BSG algorithm, finding a large subset with small doubling under a high-additive-energy condition.For E(A) ≥ |A|^3/K, it runs in (|A|^2/K^2 + K^13|A|)N^o(1) time and returns A′ with |A′| ≥ |A|/(64K) and |A′ + A′| ≤ K^16|A|·N^o(1).Source: §1.3 · p. 9
  • Theorem 1.12 deterministically finds and exactly counts sums with multiplicity at least |A|/k in O(k^2|A|^(2−3/128)N^o(1)) time.This result replaces the randomized step in the proof of Theorem 1.3, originally established using randomized reductions in [CVX23].Source: §1.3 · p. 10
  • For k-Mismatch Constellation, a win-win approach combines Fischer’s Partial Convolution algorithm [Fis24] with small-doubling #3SUM-counting when candidate shifts are numerous.When the candidate set is large, it has low doubling and a subset B′ of size at least |B| − O(k) has a small sumset with the candidates; the algorithm handles B′ and B \ B′ separately.Source: §1.3 · p. 10

1.4 Discussions and open questions

  • The authors leave open whether Text-to-Pattern Hamming Distances can reach O((1/ε)^(1−c)n^(1+o(1))): popular-sum counting is derandomized, but subsampling-error analysis remains randomized in [CJVX23].They also ask whether Theorem 1.8 can be extended to allow wildcards in both pattern and text.Source: §1.4 · p. 11
  • Derandomizing the 3SUM reduction to Distance Oracles remains open, and the authors expect a larger barrier for 4-Linear Degeneracy Testing, whose hardness in [JX23] relies on Sidon-set instances.The latter may require improving Theorem 1.1’s bound from O(n^(2+δ)) to 2n^2 − n; the Distance Oracles reduction must control longer cycles.Source: §1.4 · p. 11
  • The k-Mismatch Constellation improvement is limited to |B| ≈ |A|; whether faster algorithms exist when |B| is much smaller remains open.Source: §1.4 · p. 11

2 Preliminaries

The preliminaries establish notation for sets, multisets, vectors, convolution, and additive energy, and introduce deterministic convolution tools used later.

2 Preliminaries

  • The notation defines sumsets, difference sets, iterated sumsets, vector support, and the 0-, 1-, and infinity-norms.The k-fold sumset is defined recursively from the preceding sumset and A.Source: §2 · p. 11
  • For multisets, indicator-vector convolution counts sum representations, while modular convolution counts representations modulo m.A multiset indicator records each element’s multiplicity.Source: §2 · p. 12
  • Additive energy counts equal-sum quadruples, and E(A)E(B) ≥ E(A,B)^2 by Cauchy–Schwarz.The mixed energy E(A,B) counts pairs of representations of the same sum.Source: §2 · p. 12
  • The preliminaries call on deterministic sparse convolution and partial convolution algorithms, the latter computing selected convolution coordinates.The cited sparse-convolution lemma is attributed to Bringmann, Fischer, and Nakos; partial convolution is attributed to Fischer.Source: §2 · p. 12

3 Tool I: Deterministic Approximate 3SUM Counting

This section develops deterministic methods for approximating representation counts and uses modular hashing to control false solutions. The resulting tools yield approximate 3SUM and 4SUM counting, including additive-energy approximation.

3 Tool I: Deterministic Approximate 3SUM Counting

  • In time (ǫ^-1|A| + |B|) · N^o(1), the deterministic algorithm returns an O(ǫ^-1|A| log^2 N)-sparse vector approximating each sum count within ǫ|B|.The guarantee applies to multisets A and B of size at most N.Source: §3 · p. 12
  • In time eO((ǫ^-1|A| + |B| + |C|) · N^o(1)), a deterministic algorithm computes approximate 3SUM counts for targets in C.This is stated as the approximate 3SUM-counting corollary of the tool.Source: §3 · pp. 12–13
  • A product of small primes is chosen to isolate a constant fraction of targets and reduce false modular solutions before estimating their representation counts.The procedure seeks a modulus that reduces collisions and pseudo-solutions, then estimates counts for isolated targets.Source: §3 · p. 13
  • Deterministic approximate 4SUM counting estimates the number of quadruples satisfying a + b = c + d, with additive error ǫ(|A| + |C|)|B||D|.The result applies to multisets A, B, C, and D.Source: §3 · p. 17
  • For a set A, additive energy can be deterministically approximated with additive error ǫ|A|^3 in O(ǫ^-1|A|N^o(1)) time.The paper identifies approximate 4SUM counting as an application of the popular-sums approximation tool.Source: §3 · p. 17

4 Tool II: Deterministic 3SUM Counting for Small Doubling Sets

This section develops deterministic 3SUM counting for small-doubling sets by reducing the problem to modular computations and smaller subproblems. The algorithm uses a modulus and shifted-set cover to partition the targets before counting solutions.

4 Tool II: Deterministic 3SUM Counting for Small Doubling Sets

  • Theorem 4.1 deterministically computes (1_A ⋆ 1_B)[c] for c ∈ C and (1_C ⋆ 1_-B)[a] for a ∈ A.The stated output is computed in time involving |A + S|, |C|, and the modulus and cover parameters.Source: §4 · pp. 18, 21
  • The deterministic algorithm has an N^o(1) factor; the passage notes this can be replaced by polylog(N) if randomization is allowed.Source: §4 · p. 18
  • A modulus M can be found so that |S mod M| ≥ 0.9|S|; for this remainder set, there is a shift set ∆ with S mod M + ∆ = Z_M and |∆| ≤ (2M ln M)/|S mod M|.Source: §4 · pp. 18–19
  • The algorithm partitions C into O(log M) parts with shifts that bound the relevant modular convolution values by O(K log M).Here K is defined as |A + S|/|S|.Source: §4 · pp. 19–20
  • For each part, 3SUM solutions are decomposed by d into subproblems on A, B_d, and C_d, solved by enumeration or deterministic sparse convolution.The sets C_d can be computed in eO(|C||∆| + |A + S|) time beyond output size.Source: §4 · pp. 20–21

5 Tool III: Almost Additive Hashing with Short Seed Length

This section constructs a small hash family for deterministic enumeration, using almost k-wise independent distributions over F_p. Its hashes are almost linear and have almost k-wise independence on integer inputs subject to a no-small-relations condition.

5 Tool III: Almost Additive Hashing with Short Seed Length

  • A small hash family is needed so deterministic applications can enumerate all its functions; the construction draws on ϵ-biased sets to reduce family size.The construction is inspired by [ABF23] and [JX23], and uses ϵ-biased sets from [AGHP92].Source: §5 · p. 22

5.1 Almost k-wise independent distribution over Fm

  • The family C has size at most 4m^2p^(3k) and is constructible in eO(m^3p^(3k)) time, yielding δ-almost uniform projections for up to k independent vectors.The distribution is constructed over F_p, with p chosen small enough to fit in a machine word.Source: §5.1 · pp. 22–23

5.2 Almost linear hashing with “almost” almost k-wise independence

  • For each hash h, additive deviations h(x+y) − h(x) − h(y) lie in ∆h, whose size is at most 2^(m−1) = N^o(1).The deviation set ∆h is an iterative sumset built from the hash parameters.Source: §5.2 · p. 24
  • When x+y=z+w, the hashes of the Sidon 4-tuple are highly correlated, with the four values contained in a translate of a small iterated deviation set.Source: §5.2 · p. 24
  • The family is almost k-wise independent for integers with no 2k2^(k+1)Q^(k′−1)-relations; such independence must fail on integers with small relations.The stated condition applies to k′ ≤ k integer inputs.Source: §5.2 · pp. 24–25

6 Tool IV: Deterministic BSG Theorem in Subquadratic Time

This section gives a deterministic subquadratic-time algorithmic version of the Balog–Szemerédi–Gowers theorem. It builds on a deterministic procedure for finding small high-energy subsets and uses deterministic approximate 3SUM counting in the theorem proof.

6 Tool IV: Deterministic BSG Theorem in Subquadratic Time

  • Given E(A) ≥ |A|^3/K, Theorem 6.1 deterministically finds A′, B′ ⊆ A in O((|A|^2/K^(2r−4) + K^13|A|)N^o(1)) time.The theorem’s stated running time combines a term depending on |A|, K, and r with a K^13|A| term.Source: §6 · p. 27, §6.2 · p. 34

6.1 Finding a small high-energy subset

  • Theorem 6.2 finds a subset of A deterministically in O(K^13|A|N^o(1)) time when E(A) ≥ |A|^3/K and K ≤ R^(1/3).Its stated input also includes a size parameter R with 1 ≤ R ≤ |A|.Source: §6.1 · p. 27

6.2 Proof of Theorem 6.1

  • Given A and K ≥ 1, c ∈ (0, 1) with E(A) ≥ |A|^3/K, Corollary 6.7 deterministically finds X ⊆ A in O(|A|^2K^2c^−2N^o(1)) time, with |X| ≥ |A|/(3K).Source: §6.2 · p. 31

7 Tool V: Deterministic 3SUM Counting for Popular Sums

The section gives a deterministic algorithm that finds and exactly counts all sufficiently popular sums in 3SUM-counting. It uses iterative structure extraction and handles the remaining sums separately.

7 Tool V: Deterministic 3SUM Counting for Popular Sums

  • The algorithm finds every sum with at least |A|/k representations and exactly computes its count in O(k^2|A|^(2−3/128) N^o(1)) time.The input sets A and B are subsets of [N], each of size at most n.Source: §7 · p. 34
  • An iterative deterministic BSG procedure extracts structured subsets until the remaining set is small or has low estimated energy.The decomposition has g = O(K log K) extracted sets and leaves a remainder with energy at most 2|A|^3/K.Source: §7 · p. 34
  • For each extracted subset, the algorithm approximates its contribution, partitions candidate sums, then exactly counts sums in the extracted parts and the remainder.The extracted-part computation uses the theorem for structured sums; the remainder is handled by brute force.Source: §7 · pp. 34–35
  • Each extracted part has a bounded sumset, with |S_i + B_i| ≤ O(kK^6|B|N^o(1)).The total extracted-part running time is O(|B|^1.5 k K^6 1/6 N^o(1)).Source: §7 · p. 35

8 Deterministic Approximate Text-to-Pattern Hamming Distances

The section presents a deterministic near-linear-time algorithm for approximate Text-to-Pattern Hamming Distances. It combines approximate 3SUM-counting with a reduction for small distances and a block-based approximation.

8 Deterministic Approximate Text-to-Pattern Hamming Distances

  • O(ε^-1 m^(1+o(1))) time suffices for a deterministic (1+ε)-approximation to Text-to-Pattern Hamming Distances.The proof reduces the text to O(n/m) chunks so it can assume n = O(m).Source: §8 · pp. 36–37
  • For each symbol, approximate the text-pattern occurrence correlations and sum them to estimate each shift's Hamming distance with additive error at most εm.This already gives a (1+ε)-approximation when distances are Θ(m).Source: §8 · p. 36
  • For distances Θ(k), a near-linear reduction to strings with O(k) runs preserves additive approximation and allows error O(εk).The reduction uses the approach of Gawrychowski and Uznański.Source: §8 · p. 36
  • The small-distance method decomposes run-length blocks into dyadic blocks, approximates their correlations, and uses FFT to combine contributions.The block-correlation approximation is computed with Theorem 1.9; the total time remains O(ε^-1 m^(1+o(1))).Source: §8 · pp. 36–37

9 Deterministic 3SUM Reductions

The section constructs deterministic fine-grained reductions from general 3SUM to instances with low additive energy. It first lowers high energy, then repeatedly lowers the energy exponent until it is arbitrarily close to 2.

9.1 From high-energy to moderate-energy

  • A deterministic reduction takes general 3SUM to instances with additive energy at most n^2.95.The proof removes a large subset each iteration and gives total time O(n^1.95+o(1)).Source: §9.1 · pp. 37–38
  • The high-to-moderate reduction combines deterministic energy approximation and constructive BSG with a structured-sum test on the extracted subset.If that test finds no solution involving the subset, it is removed before the next iteration.Source: §9.1 · pp. 37–38

9.2 From moderate-energy to low-energy

  • When energy is at most n^(2+α), a deterministic reduction lowers it to n^(2+β), where β = α − α(1−α)/30.The step uses hashing to split the instance and deterministically checks candidate hash functions for a good partition.Source: §9.2 · pp. 38–40
  • For every constant δ > 0, a deterministic fine-grained reduction maps 3SUM to instances with additive energy at most n^(2+δ).The construction first reaches energy at most n^2.95, then repeatedly applies an exponent-reducing step.Source: §9.2 · p. 42
  • The low-energy reduction applies the deterministic step repeatedly; its exponent sequence converges to zero, yielding the stated bound for any constant δ.The reduction maintains polynomial universe size through its finitely many steps.Source: §9.2 · p. 42

10 Reduction to Triangle Listing

This section develops deterministic reductions from 3SUM variants to Triangle Listing, using a hashing construction and a direct-product strategy for derandomization. It also derandomizes the reduction used for 4-Cycle Listing lower bounds by reducing through Triangle Listing.

10 Reduction to Triangle Listing

  • Low-energy 3SUM reduces deterministically to n^o(1) Triangle Listing instances with bounded graph size, degree, 4-cycles, and listing threshold.For a size-n set with additive energy at most n^(2+δ) and P=n^(kε)≤n, each graph has P^2·n^O(ε) nodes, maximum degree O(n^(1+ε)/P), and n^(2+δ+o(1))/P + n^(4+o(1))/P^4 4-cycles; it must report n^(3+o(1))/P^2 triangles. Reduction time is O(n^(2−ε) + n^(1+O(ε))·P).Source: §10 · p. 42

10.1 Warm-up: randomized reduction

  • Triples (a,b,c) satisfying Eq. (25) correspond one-to-one with graph triangles; for a+b+c≠0, each contributes at most one triangle per constructed graph, whose expected false-triangle count is n^(3+o(1))/p^3.Source: §10.1 · p. 44

10.2 Derandomization

  • Derandomization selects hash functions from smaller families and combines them by direct product to retain the required reduction properties.The lemma states that suitable f, g, h exist when combined with efficiently evaluable F, G, H whose additive-error sets have size n^o(1).Source: §10.2 · p. 46
  • The proof constructs hash functions deterministically in n^(1+O(ε)) time and iterates the construction so the reduction runs in n^(1+O(ε)) + n^(2−ε) time.If a lemma fails because the input contains a 3SUM solution, the algorithm can conclude that a solution exists and still obtain the needed hash functions.Source: §10.2 · p. 51
  • Under the deterministic 3SUM hypothesis, 4-Cycle Listing has no deterministic O(n^2−δ + t) or O(m^(4/3)−δ + t) algorithm for any δ > 0, where t is the number of 4-cycles.The reduction would otherwise yield a deterministic truly subquadratic 3SUM algorithm.Source: §10.2 · p. 52
  • The reduction yields Triangle Listing instances with n^(1+O(δ/C)) nodes, maximum degree n^0.5, and n^(1.51−δ/C+o(1) + n^(2−4δ/C+o(1)) 4-cycles; listing their triangles takes n^(2−2δ/C+o(1)) time per graph.For sufficiently large C, the total reduction and listing time is O(n^(2−δ/C)), which is truly subquadratic.Source: §10.2 · p. 52
  • A standard four-copy construction converts each Triangle Listing instance into a 4-Cycle Listing instance while adding only a constant-factor increase in nodes and edges.Four-cycles using one node from each copy correspond to triangles; other four-cycles correspond to original four-cycles, each contributing O(1) new ones.Source: §10.2 · p. 52

11 k-Mismatch Constellation

The section develops algorithms for k-Mismatch Constellation, including a scaling-based derandomization, and applies them to string matching with wildcards. It also proves a combinatorial lower bound under the BMM hypothesis.

11 k-Mismatch Constellation

  • Subsampling reduces k-Mismatch Constellation to a partial convolution problem, while the section's deterministic algorithm uses scaling to remove the reduction's randomness.For the subsampling reduction, candidates retain shifts with at most k0 mismatches and exclude those above (1 + η0/20)k0 with high probability.Source: §11 · p. 53, §11.1 · p. 54, §11.2 · p. 55

11.1 Algorithm for large B

  • The large-B algorithm uses approximate convolution to separate bad elements of B, and bounds |C − C| by 5|A|L and |B′ + C| by 20|A|RL.These bounds support the partial-convolution algorithm's candidate-processing steps.Source: §11.1 · p. 54

11.2 Derandomization B by scaling

  • The scaling technique derandomizes the k-Mismatch Constellation algorithm by lifting candidate shifts through increasing moduli, with the final candidate set giving the original instance's answer.The theorem's stated regime is k ≤ 0.3|B|.Source: §11.2 · pp. 55–56

11.3 Combinatorial lower bound

  • Under the BMM hypothesis, combinatorial algorithms for k-Mismatch Constellation require n^(1+α/2−o(1)) = k n^(1−o(1)) time.The bound follows by reduction from Text-to-Pattern Hamming Distances.Source: §11.3 · pp. 56–57

11.4 Applications to k-Mismatch String Matching with Wildcards

  • For string matching with wildcards, the section gives an eO(k^(2/3)n)-time reduction and describes a modification improving the bound to eO(k^(1/2)n).The point-set encoding counts non-wildcard mismatches while wildcards make no contribution.Source: §11.4 · pp. 57–58
Loading 2410.20764v1…