PaperlayerView exact revision on arXiv

Source-linked AI summary

Fredman's Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More

Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu

arXiv:2303.14572v1cs.DS

TL;DR

The paper studies how small changes in computational problems affect fine-grained complexity and how problems are connected by reductions. It combines Fredman’s trick with triangle-based and block-reduction techniques, deriving conditional hardness results and new algorithms.

  • Problem

    Fine-grained complexity still has unanswered questions about how related problems differ in difficulty and how they are connected.

    Source: §1 · p. 4

  • Method

    The paper uses Fredman’s trick to turn witness equalities into zero-weight triangles and develops deterministic block reductions for counting 3SUM.

    Source: §5 · p. 22, §9.2 · p. 44

  • Results

    Under Strong APSP, u-dir-APSP requires n^7/3-o(1), while Min-Witness-Prod has n^7/3-o(1) conditional hardness from u-dir-APSP or n^11/5-o(1) hardness under Strong APSP.

    Source: §1.1 · p. 6

  • Takeaways & Limitations

    The new triangle-decomposition theorem applies to structured Min-Plus and 3SUM problems and yields the first truly subquartic algorithm for counting shortest paths in general weighted graphs.

    Source: §1.1 · p. 7

    The techniques do not yet establish equivalences between decision and counting for CNF-SAT and OV.

    Source: §9.4 · p. 46

Abstract

from arXiv · show

In this paper we carefully combine Fredman's trick [SICOMP'76] and Matou\v{s}ek's approach for dominance product [IPL'91] to obtain powerful results in fine-grained complexity: - Under the hypothesis that APSP for undirected graphs with edge weights in $\{1, 2, \ldots, n\}$ requires $n^{3-o(1)}$ time (when $\omega=2$), we show a variety of conditional lower bounds, including an $n^{7/3-o(1)}$ lower bound for unweighted directed APSP and an $n^{2.2-o(1)}$ lower bound for computing the Minimum Witness Product between two $n \times n$ Boolean matrices, even if $\omega=2$, improving upon their trivial $n^2$ lower bounds. Our techniques can also be used to reduce the unweighted directed APSP problem to other problems. In particular, we show that (when $\omega = 2$), if unweighted directed APSP requires $n^{2.5-o(1)}$ time, then Minimum Witness Product requires $n^{7/3-o(1)}$ time. - We show that, surprisingly, many central problems in fine-grained complexity are equivalent to their natural counting versions. In particular, we show that Min-Plus Product and Exact Triangle are subcubically equivalent to their counting versions, and 3SUM is subquadratically equivalent to its counting version. - We obtain new algorithms using new variants of the Balog-Szemer\'edi-Gowers theorem from additive combinatorics. For example, we get an $O(n^{3.83})$ time deterministic algorithm for exactly counting the number of shortest paths in an arbitrary weighted graph, improving the textbook $\widetilde{O}(n^{4})$ time algorithm. We also get faster algorithms for 3SUM in preprocessed universes, and deterministic algorithms for 3SUM on monotone sets in $\{1, 2, \ldots, n\}^d$.

1 Introduction

The introduction examines the fine-grained complexity of unweighted directed APSP, Min-Witness-Prod, and exact counting, presenting conditional lower bounds and decision–counting equivalences. It also describes new BSG-based algorithms and their applications to shortest-path counting and 3SUM and triangle problems.

1 Introduction

  • The introduction motivates these results by unresolved gaps between directed and undirected APSP and between decision and exact counting, and asks how BSG-based and direct approaches to structured Min-Plus problems relate.It notes that the BSG-based approach applies to preprocessed-universe 3SUM and multidimensional monotone-set 3SUM, unlike subsequent direct approaches.Source: §1 · pp. 4–6

1.1 Summary of Our Contributions and New Tool

  • Min-Plus-Product and Exact-Weight Triangle are subcubically equivalent to their counting versions, while 3SUM is subquadratically equivalent to its counting version.The paper presents these as the first fine-grained equivalences between exact counting and decision variants.Source: §1.1 · pp. 6–7
  • A new decomposition theorem for zero-weight triangles substitutes for the BSG Theorem and yields a truly subquartic algorithm for counting general weighted APSP, alongside applications to structured Min-Plus and 3SUM problems.The theorem also gives an improved BSG bound for some parameter ranges and a faster algorithm for 3SUM with preprocessed universes.Source: §1.1 · p. 7
  • The paper combines Fredman’s trick with Matoušek’s dominance/equality-product technique, splitting few- and many-witness cases and using witness finding, hitting sets, and frequency-based handling.The combination is designed to exploit fast matrix multiplication and handle counting even when the number of solutions is large.Source: §1.1 · pp. 7–8

1.2 Conditional Lower Bounds for Unweighted Directed APSP, Min-Witness Product and Other Problems with Intermediate Complexity

  • Under the Strong APSP Hypothesis, u-dir-APSP requires n^(7/3-o(1)) time and Min-Witness-Prod requires n^(11/5-o(1)) time; under the u-dir-APSP Hypothesis, Min-Witness-Prod requires n^2.223 time.When ω = 2, the latter lower bound becomes n^(7/3-o(1)); the Strong APSP Hypothesis also yields a tight lower bound for sufficiently sparse u-dir-APSP graphs.Source: §1.2 · pp. 9–10
  • Under the Strong APSP Hypothesis, the paper derives conditional lower bounds for additional problems, including shortest-lightest paths, batched range mode, and dynamic shortest paths in planar graphs.For sufficiently sparse directed graphs, the repeated-BFS O(mn) algorithm for u-dir-APSP is essentially optimal under the same hypothesis.Source: §1.2 · pp. 9–10
  • Unlike earlier work [LPV20] [CVX21], this work reduces u-dir-APSP to Min-Witness-Prod and obtains higher lower bounds for other problems, broadening the hypothesis’s use for conditional lower bounds.Source: §1.2 · p. 10
  • Min-Equal-Convolution requires n^1+1/6-o(1) time under the Strong APSP Hypothesis, n^1+ρ/2-o(1) under the u-dir-APSP Hypothesis, or n^1+1/11-o(1) under the Strong Min-Plus Convolution Hypothesis.The lower bound under the Strong Min-Plus Convolution Hypothesis uses a new BSG variant.Source: §1.2 · p. 10

1.3 Equivalence of Counting and Detection

  • #3SUM and 3SUM are equivalent under truly subquadratic reductions; #Min-Plus-Product and Min-Plus-Product, Exact-Tri and #Exact-Tri, and #mod UAPSP and APSP are equivalent under truly subcubic reductions.For #mod UAPSP, the equivalence holds for any O(poly log n)-bit integer U ≥ 2.Source: §1.3 · pp. 11–12
  • The paper gives the first nondeterministic algorithms beating essentially cubic or quadratic deterministic algorithms for #Neg-Tri, #Exact-Tri, and #3SUM with real-valued inputs, and the first truly subquadratic quantum algorithm for #3SUM.The quantum result follows by combining the eO(n) quantum 3SUM algorithm with the subquadratic equivalence between 3SUM and #3SUM.Source: §1.3 · p. 12

1.4 New Variants of the BSG Theorem with Algorithmic Applications

  • The Triangle Decomposition Theorem partitions zero-target triangles into O(s^3) subgraphs plus O(n^3/s) remainder triangles, with every triangle in each subgraph having the target weight.A new BSG form replaces the sum-set bound O(s^6 n) with eO(s^2 n^3/2), improving an application to preprocessed-universe 3SUM.Source: §1.4 · pp. 12–13
  • O(n^3.83) time counts shortest paths between every vertex pair in arbitrary weighted graphs, the first truly subquartic algorithm for this problem.The paper also gives eO(n^15/4) time when ω = 2.Source: §1.4 · p. 13
  • With eO(n^2) expected preprocessing, 3SUM query time falls to eO(n^11/6); preprocessed Exact-Tri queries take O(n^2.83) after eO(n^3) preprocessing.The 3SUM query bound also applies when C′ is an arbitrary set of n integers.Source: §1.4 · pp. 13–14
  • For monotone sets in [n]^d, the paper gives the first deterministic 3SUM algorithm for every constant d, running in O(n^2−1/O(d)) time.The authors note the bound is not faster than the prior randomized bound, but the approach is simpler and deterministic.Source: §1.4 · p. 14

2 Problem Definitions

This section establishes notation and the computational model, then defines the paper’s graph, matrix, additive, and counting problems. It also specifies how counting variants relate to their decision or optimization counterparts.

Problem Definitions

  • The notation [n] and [±n] denotes integer ranges, [X] is the indicator of a predicate, and the model uses O(log n)-bit words and input integers unless stated otherwise.M(n1,n2,n3) denotes randomized matrix multiplication time.Source: §2 · pp. 14–15
  • Min-Plus-Product outputs each entry as the minimum over summed matrix entries, while Min-Plus-Convolution applies the same operation to arrays; APSP computes all-pairs shortest-path distances.The section also defines the bounded-entry Min-Plus product running-time notation.Source: §2 · p. 15
  • Exact-Tri and Neg-Tri ask whether a weighted graph contains a triangle meeting a target-sum or negative-sum condition, while Exact-k-Clique and Min-k-Clique concern clique weight sums.The all-edges Exact-Tri variant answers the target-sum question separately for each edge.Source: §2 · p. 15
  • 3SUM tests whether a+b=c across three sets, with all-numbers, convolution, and monotone-convolution variants asking for answers across targets or array positions.The convolution variants constrain indices to sum to the queried position; Mono-Convolution additionally requires the selected values to be equal.Source: §2 · p. 15
  • Counting variants replace each existence bit with the number of qualifying objects, or each optimum with its number of optimal solutions; examples include #Min-Plus-Product and shortest paths modulo U.The text notes that detection counting variants are at least as hard as detection, but this is not obviously true for minimization problems.Source: §2 · pp. 15–16
  • u-dir-APSP computes directed unweighted all-pairs distances, while Min-Witness-Prod returns the smallest shared Boolean-matrix index and equality-product variants find indices satisfying matrix-entry equality.Min-Equal-Prod returns the smallest matching value rather than the smallest matching index.Source: §2 · p. 16
  • undir-APSLP1,2 and undir-APLSP1,2 distinguish lexicographic path objectives on edge weights 1 or 2; Batch-Range-Mode answers interval queries, and Min-Equal-Convolution compares array entries.The two APSLP definitions reverse whether the fewest edges or lowest weight is optimized first.Source: §2 · p. 16

3 Conditional Lower Bounds for Problems with Intermediate Complexity: u-dir-APSP under the Strong APSP Hypothesis

The section reduces bounded-entry Min-Plus product to unweighted directed APSP by combining Fredman’s trick with equality products. Under the Strong APSP Hypothesis, this yields conditional lower bounds for directed APSP and related Min-Plus problems.

3 Conditional Lower Bounds for Problems with Intermediate Complexity: u-dir-APSP under the Strong APSP Hypothesis

  • The reduction focuses on solving bounded-integer Min-Plus product and uses an APSP oracle only at the end; Fredman’s trick also remains useful for restricted integer ranges.A naive hashing approach to shrink the range does not work for Min-Plus product, although it may work for equality-type problems such as AE-Exact-Tri.Source: §3 · p. 16, §3.2 · p. 18

3.1 Preliminaries: Generalized Equality Products

  • Generalized equality products can be computed in eO(min_r(n1n2n3/r + M(n1,rn2,n3))); for square matrices the bound is eO(n^(3+ω)/2).The section uses this technique as a component of its reductions.Source: §3.1 · p. 17

3.2 The Key Reduction

  • The key reduction replaces a bounded-entry Min-Plus product with instances having smaller inner dimension s and entry range [t], at a cost governed by three terms.The stated cost is (n2/s)M*(n1,s,n3|t) + sn1n2n3/r + sM*(n1,rn2,n3|ℓ/t).Source: §3.2 · p. 17

3.3 Consequences

  • For rectangular Min-Plus product with dimensions n×n^β and n^β×n and entries in [n^(2β)], the conditional lower bound is n^(2+β−ε), matching the obvious O(n^(2+β)) upper bound.This bound follows under the Strong APSP Hypothesis.Source: §3.3 · p. 19
  • Under the Strong APSP Hypothesis, unweighted directed APSP needs n^(7/3−ε) time, and with n^(1+β) edges needs n^(2+β−ε) time for β≤1/3.The dense bound assumes 1/3≤(3−ω)/2, a condition the paper says can be removed later; the sparse bound has the same removable condition.Source: §3.3 · p. 19
  • The same approach is used to derive conditional lower bounds for Min-Witness-Prod, undir-APLSP1,2, and Batch-Range-Mode.These reductions use both the Strong APSP Hypothesis and the u-dir-APSP Hypothesis.Source: §3.3 · p. 19

4 Equivalences Between Counting and Detection Problems: #Exact-Triangle vs. Exact-Triangle

This section shows that detecting exact-weight triangles and counting them are subcubically equivalent. Its reduction combines witness listing, a hitting set, and equality-product computations.

4 Equivalences Between Counting and Detection Problems: #Exact-Triangle vs. Exact-Triangle

  • The paper combines Fredman’s trick with Equality Product to extend the detection-counting equivalence approach to #3SUM and 3SUM, with further technical ideas required for that reduction.The #3SUM and 3SUM equivalence is described as subquadratic.Source: §4 · pp. 20–21
  • When a selected set S intersects a pair’s witness set, the equality-product method computes that pair’s exact witness count in eO(|S|·n^((3+ω)/2)) time.The method uses weights to form equality-product matrices and returns the count for pairs hit by S.Source: §4 · p. 20
  • An O(n^(3−ε)) algorithm for AE-Exact-Tri yields an O(n^(3−ε′)) algorithm for #AE-Exact-Tri, for some ε′>0.The construction lists up to n^0.99 witnesses per pair, then uses a hitting set and a witness-counting lemma for the remaining pairs.Source: §4 · p. 20
  • Exact-Triangle and #Exact-Triangle are subcubically equivalent.The reduction from counting to detection passes through #AE-Exact-Tri and AE-Exact-Tri, then uses known reductions.Source: §4 · p. 20

5 Alternative to BSG: A Triangle Decomposition Theorem and Its Applications

The section introduces a deterministic triangle decomposition as an alternative to the BSG theorem and applies it to preprocessed Exact-Triangle and 3SUM, bounded monotone 3SUM, and #APSP.

5 Alternative to BSG: A Triangle Decomposition Theorem and Its Applications

  • The triangle decomposition partitions zero-weight triangles into a small explicit set R and subgraphs, with eO(s^3) subgraphs and eO(n1n2n3/s) triangles in R.The subgraphs and R are constructed deterministically; if U–V edge weights change, they can be updated in eO(n1n2n3/s+s^2n1n3) time.Source: §5 · p. 21

5.1 Application 1: Exact Triangle in Preprocessed Universes

  • After preprocessing a real-weighted tripartite graph, AE-Exact-Tri’ queries take eO(n1n2n3/s+sM(n1,s^2n2,n3)); for equal part sizes, the paper gives O(n^2.83), or eO(n^(11/4)) if ω=2.AE-Exact-Tri’ reports whether each U×V edge belongs to an exact triangle.Source: §5.1 · p. 22

5.2 Application 2: 3SUM in Preprocessed Universes

  • For sets of n integers in [n^O(1)], deterministic eO(n^2) preprocessing supports All-Nums-3SUM queries in O(n^1.891), or eO(n^(11/6)) if ω=2.Queries may specify arbitrary subsets of each of the three preprocessed sets.Source: §5.2 · p. 23

5.3 Application 3: A Deterministic 3SUM Algorithm for Bounded Monotone Sets

  • For monotone sets in [n]^d with constant d≥2, All-Nums-3SUM has a deterministic O(n^(2−1/O(d))) algorithm.The result is the first truly subquadratic deterministic algorithm for bounded monotone 3SUM in arbitrary constant dimensions.Source: §5.3 · pp. 23–24
  • The theorem also yields subquadratic algorithms for monotone or bounded-difference Min-Plus convolution and subcubic algorithms for corresponding Min-Plus products.The paper omits the details because earlier algorithms for these problems already existed.Source: §5.3 · p. 24

5 Alternative to BSG: A Triangle Decomposition Theorem and Its Applications

  • The decomposition offers a simpler, more elementary alternative to BSG for many subquadratic results, though BSG may still help optimize exponents.The paper notes that the decomposition also supports exact counting in preprocessed-universe applications, unlike the cited prior BSG-based method for 3SUM there.Source: §5.2 · p. 23, §5.3 · p. 24

5.4 Application 4: A Truly Subquartic #APSP Algorithm

  • For positive-edge-weight graphs, #APSP runs in O(n^3.83), or eO(n^(15/4)) if ω=2.The paper presents this as the first truly subquartic algorithm for #APSP on arbitrary weighted graphs.Source: §5.4 · p. 24

6 More Lower Bounds under the Strong APSP Hypothesis

Under the Strong APSP Hypothesis, Lemma 6.1 extends lower-bound implications beyond prior parameter restrictions. The section transfers these implications to Min-Witness-Prod, shortest-lightest paths, range mode, and offline planar dynamic shortest paths.

6 More Lower Bounds under the Strong APSP Hypothesis

  • Lemma 6.1 removes the β ≤ (3 − ω)/2 restriction, extending Corollary 3.5 to all β ≤ 1/3; when ω = 2, the u-dir-APSP Hypothesis implies the Strong APSP Hypothesis.The section also states that the directed and undirected versions of the Strong APSP Hypothesis are equivalent.Source: §6 · p. 25

6.1 Min-Witness Product

  • n^11/5−ε time is impossible for Min-Witness-Prod under the Strong APSP Hypothesis; for ω = 2, this makes it strictly harder than Boolean matrix multiplication.For inner dimension n^γ with γ ≤ 0.3138, the section also establishes strict hardness relative to Boolean matrix multiplication.Source: §6.1 · p. 26

6.2 All-Pairs Shortest Lightest Paths

  • A reduction encodes Min-Plus entries as paths so that the shortest among equal-length lightest paths has weight 2y + 2 + min_k(a_ik + b_kj).The constructed graph has O(n) nodes and O(nx) edges when xy^2 ≤ n.Source: §6.2 · pp. 26–27
  • n^11/5−ε time is impossible for undir-APSLP1,2 under the Strong APSP Hypothesis; for sufficiently sparse graphs, its naive algorithm is essentially optimal.The result also applies to undir-APLSP1,2.Source: §6.2 · p. 27

6.3 Batched Range Mode

  • N^7/6−ε time is impossible for N batched range-mode queries on N elements under the Strong APSP Hypothesis.For universe size σ = N^γ and γ ≤ 1/6, the lower bound is tight against the known O(Nσ) upper bound; the section also extends results to range minority.Source: §6.3 · p. 28

6.4 Dynamic Shortest Paths in Unweighted Planar Graphs

  • An offline sequence of N shortest-path queries and N updates on an unweighted, undirected N-node planar graph requires N^6/5−ε time under the Strong APSP Hypothesis.This is the first conditional lower bound for this unweighted problem in the offline setting; the technique yields nontrivial bounds for general noncombinatorial algorithms in offline or batched settings.Source: §6.4 · p. 29

6.5 Min-Witness Equality Product

  • The section also gives an alternative Min-Witness-Eq-Prod lower bound: an O(n^(2ω+5)/4−ε) algorithm would imply a truly subcubic Min-Plus product.The exponent is strictly larger than ω for ω in [2, 2.373), so this bound is better when the current upper bound on ω is close to tight, but worse at ω = 2.Source: §6.5 · pp. 29–30

7 Lower Bounds under the u-dir-APSP Hypothesis

The u-dir-APSP Hypothesis yields conditional lower bounds for several intermediate-complexity problems. The section also relates this hypothesis to rectangular Min-Plus products and obtains an equivalence for a range of product dimensions.

7 Lower Bounds under the u-dir-APSP Hypothesis

  • For any constant β, an O(n^2+β−ε) algorithm for the specified rectangular Min-Plus product would imply an O(n^2+ρ−Ω(ε)) algorithm for u-dir-APSP.The reduction’s parameter κ is defined using rectangular matrix-multiplication exponents; the section chooses σ = 0.85 and uses the bound ω(1, 0.85, 1) < 2.258317.Source: §7 · p. 30

7.1 Min-Witness Product

  • When ω = 2, n^7/3−ε time is impossible for Min-Witness-Prod under the u-dir-APSP Hypothesis; the bound is n^2.223 regardless of ω.For rectangular Min-Witness-Prod with inner dimension n^γ, the lower bound is O(n^2+0.223γ−ε) for γ ≤ 1.Source: §7.1 · p. 31

7.2 All-Pairs Shortest Lightest Paths

  • When ω = 2, n^7/3−ε time is impossible for undir-APSLP1,2 under the u-dir-APSP Hypothesis, and the same bound holds for undir-APLSP1,2.The result supplies conditional lower bounds for both problems without relying on zero-weight edges.Source: §7.2 · p. 31

7.3 Batched Range Mode

  • For N queries on N elements, the range-mode lower bound is N^5/4−ε when ω = 2, or N^(1+ρ/2)−ε regardless of ω.For any Q ≤ N^2, the section gives an O(Q^3/4 N^1/2−ε) lower-bound threshold when ω = 2, and O(Q^(1−0.365/2)N^0.365−ε) regardless.Source: §7.3 · p. 31

7.4 Dynamic Shortest Paths in Planar Graphs

  • An offline sequence of N shortest-path queries and N updates on an unweighted, undirected N-node planar graph requires N^5/4−ε time when ω = 2, or N^1.211 time regardless, under the hypothesis.The section states that these bounds are slightly better than those obtained from the Strong APSP Hypothesis.Source: §7.4 · p. 32

7.5 An Equivalence Result

  • For ω = 2, u-dir-APSP has an O(n^2.5−ε) algorithm if and only if the specified rectangular Min-Plus product has an eO(n^2+β−ε′) algorithm, for any constant β in (0, 1).More generally, the section establishes equivalence between the corresponding product claims for any two dimensions in (0, α).Source: §7.5 · p. 32

8 More Equivalences Between Counting and Detection Problems

This section develops fine-grained equivalences between counting and detection for Min-Plus Product, convolution problems, and All-Nums 3SUM, and presents a randomized method for counting high-witness 3SUM-Convolution outputs. It also contrasts these equivalences with Negative Triangle and discusses their potential to enable average-case hardness results for decision problems.

8.1 Min-Plus Product

  • Min-Plus Product and #Min-Plus-Product are subcubically equivalent: a truly subcubic algorithm for either yields one for the other.The counting-to-detection reduction encodes each unique minimizing witness through O(log n) rounds that recover its index.Source: §8.1 · p. 33

8.2 3SUM Convolution and Min-Plus Convolution

  • eO(n^((9+ω)/4)/L) randomized time suffices to count every All-Nums-3SUM-Convolution output with at least L witnesses.The method randomizes indices over a finite field, partitions them into intervals, and uses triangle-witness counting to handle high-witness outputs.Source: §8.2 · pp. 34, 36
  • All-Nums-3SUM-Convolution is subquadratically equivalent to its counting version, and Min-Plus-Convolution is likewise subquadratically equivalent to #Min-Plus-Convolution.The counting algorithms use the corresponding detection algorithms for outputs with few witnesses and the high-witness counting method for the rest.Source: §8.2 · p. 36

8.3 All-Numbers 3SUM

  • A truly subquadratic All-Nums-3SUM algorithm yields a randomized truly subquadratic algorithm for #All-Nums-3SUM, so 3SUM and #3SUM are subquadratically equivalent.The reduction passes through 3SUM-Convolution and its counting version.Source: §8.3 · p. 37

8.4 Discussion

  • Counting Negative Triangle even mod 2 solves Exact-Tri [AFW20], while reducing #Neg-Tri to Neg-Tri would imply a surprising 3SUM-to-APSP reduction.The implication follows from Neg-Tri’s subcubic equivalence to APSP and the reductions from 3SUM to Exact-Tri and Exact-Tri to #Neg-Tri [AFW20].Source: §8.4 · p. 37
  • The paper’s equivalences for Min-Plus-Product and Exact-Tri with their counting variants suggest Neg-Tri may behave differently; equating Neg-Tri with #Neg-Tri would make 3SUM-to-APSP more plausible.Source: §8.4 · p. 37
  • Known worst-case-to-average-case techniques for fine-grained problems work only for counting problems, while public-key protocol design appears to require decision variants hard on average.The discussion situates this issue in work on fine-grained cryptography and worst-case-to-average-case reductions [DLV20].Source: §8.4 · p. 37
  • If #Exact-Tri or #3SUM were shown hard on average, the paper’s reductions back to Exact-Tri and 3SUM would yield distributions where those decision problems are hard, potentially enabling public-key protocols.Source: §8.4 · p. 38

9 Counting Algorithms in Other Models

The section extends counting algorithms across integer and real inputs and quantum computation, with algorithms developed for several counting problems under specified models. It also examines limits on deriving counting–decision equivalences and conditional barriers to fine-grained reductions for CNF-SAT and OV.

9.1 Co-Nondeterministic Algorithms for Counting Problems with Integer Inputs

  • #AE-Neg-Tri reduces deterministically to O(log n) #AE-Exact-Tri instances in eO(n^2) time, and the two counting problems are subcubically equivalent.The reduction preserves each edge’s count by summing the corresponding counts across instances.Source: §9.1 · pp. 38–39
  • #AE-Exact-Tri and #AE-Neg-Tri with integer weights in [±n^α] lie in (N ∩ coN)TIME[eO(n^(3+ω)/2)] for any constant α.The verifier uses the nonpositive-to-exact reduction and a modular-prime check.Source: §9.1 · pp. 39–40
  • #All-Nums-3SUM on size-n integer sets in [±n^α] lies in (N ∩ coN)TIME[eO(n^1.5)] for any constant α.The verifier reduces positive and negative counts to O(log n) instances and sets q = 0.5.Source: §9.1 · p. 40

9.2 Co-Nondeterministic Algorithms for Counting Problems with Real Inputs

  • The real-input algorithms assume a Reasonable Real RAM, including low-degree predicates; a modified Exact-Tri definition permits 4-linear comparisons.Integer parts of the computation allow Word RAM operations with O(log n)-bit words.Source: §9.2 · p. 40
  • For real inputs, #AE-Real-Exact-Tri and #AE-Real-Neg-Tri lie in (N ∩ coN)TIME with the theorem’s runtime unspecified in the supplied passage.The section also introduces co-nondeterministic algorithms for Equality-Product and Dominance-Product on a specified subset of entries.Source: §9.2 · pp. 41–42
  • #All-Nums-Real-3SUM reduces deterministically to a matrix-counting problem, and has a truly subquadratic randomized algorithm on an unrestricted Real RAM without floor.The paper also gives a co-nondeterministic algorithm for #All-Nums-Real-3SUM; its stated running-time expression is incomplete in the supplied passage.Source: §9.2 · p. 44

9.3 Quantum Algorithms for Counting Problems

  • An eO(n^2−ε)-time quantum algorithm for #3SUM follows from the subquadratic quantum algorithm for 3SUM and the paper’s counting–detection equivalence.The 3SUM algorithm is attributed to [AL20].Source: §9.3 · p. 46

9.4 Discussion

  • Under NSETH, no deterministic fine-grained reductions can map CNF-SAT or OV to #Exact-Tri, #APSP, or #3SUM.The paper’s techniques do not establish decision–counting equivalences for CNF-SAT or OV; whether such equivalences exist remains open.Source: §9.4 · p. 46

10 BSG Theorems Revisited

The section revisits Balog–Szemerédi–Gowers (BSG) covering theorems and develops new versions aimed at simpler constructions and better algorithmic bounds. It applies these covers to preprocessed-universe 3SUM and presents a separate reinterpretation of Gowers’s proof.

10.1 A New Simpler Version

  • The new BSG covering bound is eO(s2n^3/2), with a direct construction that avoids repeated subset extraction and improves applications when s ≫ n^1/8.The proof focuses on indexed sets; its construction can be made Las Vegas randomized in eO(n2) time.Source: §10.1 · pp. 47–48
  • The cover uses eO(s3) subsets and eO(n2/s) exceptional pairs to cover all pairs (a, b) with a − b ∈ C.The indexed-set construction takes eO(n2) Las Vegas randomized time.Source: §10.1 · p. 48
  • For the simpler cover, Fredman’s trick and random shifts split pairs into few-witness, low-frequency, and high-frequency cases.The proof bounds the expected total difference-set size by eO(s2n^3/2).Source: §10.1 · pp. 47–49

10.2 Application: Improved 3SUM in Preprocessed Universes

  • Chan and Lewenstein’s approach has applications to preprocessed-universe and monotone-set 3SUM that subsequent approaches do not handle.The section improves the preprocessed-universe query bound over the prior eO(n13/7) result.Source: §10.2 · p. 49
  • Preprocessing three n-integer sets in eO(n2) Las Vegas randomized time supports All-Nums-3SUM queries on arbitrary subsets in eO(n11/6) time.The same query bound holds when C′ is an arbitrary n-integer set and C is not supplied during preprocessing.Source: §10.2 · p. 49

10.3 Reinterpreting Gower’s Version

  • The Gowers-based cover also uses eO(s3) subsets and eO(n2/s) exceptional pairs, and its construction takes eO(n2) Las Vegas randomized time.The authors use this direct-cover reinterpretation in a later conditional lower-bound application.Source: §10.3 · pp. 50–51
  • A many-witness variant uses eO(s2ŝ) subsets and eO(n2/ŝ) exceptional pairs, with Monte Carlo construction time eO(n2/ŝ + s2ŝn).It gives subquadratic construction for a variant requiring only the many-witness case.Source: §10.3 · p. 51

11 Lower Bounds for Min-Equality Convolution

This section establishes conditional lower bounds for Min-Equal-Convolution by reductions from APSP and Min-Plus Convolution problems. The bounds rely in part on a Gowers-based BSG covering variant for handling many-witness cases.

11 Lower Bounds for Min-Equality Convolution

  • Under the Strong APSP Hypothesis, Min-Equal-Convolution on length-n arrays requires n^(1+1/6−o(1)) time.The reduction proceeds through conditional hardness for u-dir-APSP.Source: §11 · p. 52
  • Under the u-dir-APSP Hypothesis, Min-Equal-Convolution requires n^(1+ρ/2−o(1)) time, or n^(1.25−o(1)) time if ω = 2.Here ρ satisfies ω(1, ρ, 1) = 1 + 2ρ.Source: §11 · p. 53
  • Under the Strong Min-Plus Convolution Hypothesis, Min-Equal-Convolution on length-n arrays requires n^(1+1/11−o(1)) time.The proof reduces bounded-entry Min-Plus Convolution to Min-Equal-Convolution.Source: §11 · p. 53
  • The Strong Min-Plus Convolution lower bound uses the Gowers-based BSG cover; the simpler cover would leave a term that prevents a subquadratic running time.The proof combines this cover with a sparse-convolution approach for small-witness cases.Source: §11 · pp. 52, 55

A.1 Exact k-Clique and Minimum k-Clique

The appendix shows that exact and minimum k-clique problems are subexponentially equivalent to their counting versions in the stated sense: a faster counting algorithm yields a faster decision algorithm. The reductions use witness listing or recover a unique minimum clique through repeated counting queries.

A.1 Exact k-Clique and Minimum k-Clique

  • An O(n^(k−ε)) algorithm for #Exact-k-Clique yields an O(n^(k−ε′)) algorithm for Exact-k-Clique for some ε′ > 0.The reduction lists few witnesses directly and uses #AE-Exact-Tri counting for cases with many witnesses.Source: §A.1 · pp. 63–64
  • An O(n^(k−ε)) algorithm for #Min-k-Clique yields an O(n^(k−ε′)) algorithm for Min-k-Clique for some ε′ > 0.The proof makes the minimum clique unique and recovers its vertices through repeated counting queries.Source: §A.1 · p. 64
  • The minimum-clique reduction first transforms weights so the unique minimum clique remains a minimum clique in the original graph.Duplicating vertices according to their bits reveals the unique clique through counts of minimum-weight cliques.Source: §A.1 · p. 64

A.2 Monochromatic Convolution

The appendix establishes a randomized fine-grained equivalence between Mono-Convolution and its counting version. It uses a number-preserving reduction through All-Nums-3SUM.

A.2 Monochromatic Convolution

  • An O(n^(1.5−ε)) Mono-Convolution algorithm yields an O(n^(1.5−ε′)) randomized algorithm for #Mono-Convolution for some ε′ > 0.The reduction preserves the number of solutions when converting All-Nums-3SUM to Mono-Convolution.Source: §A.2 · p. 64
  • A subquadratic Mono-Convolution algorithm implies a truly subquadratic 3SUM algorithm, which gives a subquadratic counting algorithm for All-Nums-3SUM.The argument invokes the paper’s Theorem 8.10 for the counting step.Source: §A.2 · p. 64
  • The reduction from All-Nums-3SUM to Mono-Convolution preserves the number of solutions, so it applies to their counting versions.Source: §A.2 · p. 64

A.3 All-Pairs Shortest Paths

This appendix establishes subcubic equivalences between APSP and counting variants, and uses counting Min-Plus Product to compute an auxiliary paired matrix product.

A.3 All-Pairs Shortest Paths

  • A truly subcubic APSP algorithm yields a truly subcubic algorithm for #mod UAPSP for any eO(1)-bit integer U ≥ 2.The implication holds for positive edge weights.Source: §A.3 · p. 65
  • A truly subcubic APSP algorithm also enables a truly subcubic algorithm for the auxiliary paired matrix product with eO(1)-bit auxiliary entries.The reduction uses counting Min-Plus Product; each auxiliary output encodes witness counts multiplied by 2^(p+q).Source: §A.3 · p. 65
  • A truly subcubic algorithm for #mod cAPSP, for eO(1)-bit c ≥ 2, implies a truly subcubic algorithm for APSP.The argument passes through counting Min-Plus Product and then Min-Plus Product.Source: §A.3 · p. 65

B Bounded-Difference or Monotone Min-Plus Product from the Triangle Decomposition Theorem

The Triangle Decomposition Theorem gives a truly subcubic Min-Plus Product algorithm for bounded-difference matrices, with extensions to exceptional pairs and monotone matrices.

B Bounded-Difference or Monotone Min-Plus Product from the Triangle Decomposition Theorem

  • The authors note that existing algorithms are faster, while their presentation is simpler and conceptually clarifies why a subcubic algorithm is possible.This claim is framed as a pedagogical perspective, without optimizing the running-time exponent.Source: B Bounded-Difference or Monotone… · p. 66
  • The algorithm samples indices divisible by ℓ, rounds values, and restricts relevant offsets Δ to {0, 1, 2}.The offset restriction follows because larger rounded sums exceed the current upper bound on the true minimum.Source: B Bounded-Difference or Monotone… · p. 66
  • For each offset, a weighted tripartite graph encodes the candidate sums and is processed with the Triangle Decomposition Theorem.The graph uses rounded A and B entries as edge weights and a rounded estimate of C as the third edge weight.Source: B Bounded-Difference or Monotone… · p. 66
  • For constant c0, bounded-difference Min-Plus Product takes eO(n^((15+ω)/6)) time, which is truly subcubic.The theorem assumes adjacent entries in every row of A and every column of B differ by at most c0.Source: B Bounded-Difference or Monotone… · p. 66
  • The method remains truly subcubic with O(n^(2−δ)) exceptional pairs violating the bounded-difference condition, for an appropriate choice of ℓ and s.The stated running time includes an additional cost for handling those exceptional pairs.Source: B Bounded-Difference or Monotone… · p. 67
  • Monotone matrices with integer entries in [n] also admit a truly subcubic algorithm through reduction to the bounded-difference case.The reduction allows a nonconstant c0 and O(n^(2−δ)) exceptional pairs, with a slightly worse final exponent.Source: B Bounded-Difference or Monotone… · p. 67

C More on BSG

This appendix extends BSG-style results for abelian groups, including a covering bound, a subset-extraction bound, and a zero-weight triangle structure theorem.

C More on BSG

  • For arbitrary subsets A and C of an abelian group, the proof can be modified to extend the result beyond indexed sets if construction time is ignored.The appendix says this requires a more careful argument in the low-frequency case.Source: C More on BSG · p. 67
  • The simpler BSG covering theorem gives eO(s^3) subsets and a residual set of eO(n^2/s) pairs covering the specified difference pairs.The stated containment is that pairs (a, b) with a − b ∈ C lie in R ∪ S.Source: C More on BSG · p. 67
  • For the Chan–Lewenstein biclique-cover problem [CL15], Theorem C.1 improves the upper bound to eO(n^(11/6)).The comparison concerns the cost function based on the sum of |A(λ) + B(λ)|.Source: C More on BSG · p. 68
  • If at least n^2/s pairs have difference in C, the simpler BSG theorem extracts A′ of size Ω(n/s), with |A′ − A′| bounded by O(s^(1/2)n^(3/2)).The stated difference-set bound is better than O(s^5n) when s ≫ n^(1/9), though that comparison is to a bound in the bichromatic sum-set setting.Source: C More on BSG · p. 68
  • If a real-weighted tripartite graph has Ω(n^3/s) zero-weight triangles, it contains a subgraph with eΩ(n^3/s^4) triangles, all zero-weight.The resulting subgraph has eΩ(n^2/s^4) edges.Source: C More on BSG · p. 69
Loading 2303.14572v1…