PaperlayerView exact revision on arXiv

Source-linked AI summary

Hardness for Triangle Problems under Even More Believable Hypotheses: Reductions from Real APSP, Real 3SUM, and OV

Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu

arXiv:2203.08356v2cs.CCcs.DS

TL;DR

The paper asks whether meaningful lower bounds can rest on weaker hypotheses, including real-valued APSP and 3SUM assumptions. It develops reductions involving All-Color-Pairs Triangle Collection and Colorful-BMM, and proves conditional hardness for ACP-Tri and flow problems.

  • Problem

    The paper asks whether lower bounds based on integer APSP and 3SUM extend to their real-valued variants and whether weaker assumptions still yield meaningful hardness.

    Source: §1 · pp. 2–3, §1.1.1 · p. 6

  • Method

    The paper develops reductions around Triangle Collection, including a Colorful-BMM generalization and a Salem-Spencer encoding for edge-colored triangles.

    Source: §1.1.3 · p. 8, §2.3 · p. 16, §8.2 · p. 35

  • Results

    n^2+δ−o(1) time is required for ACP-Tri under Hypothesis 2 in a reasonable Real RAM; conditional lower bounds also cover dynamic and ST-Max Flow.

    Source: §1.1.1 · p. 6

  • Takeaways & Limitations

    Under Hypothesis 2, fully dynamic #SSR, #SCC, #SS-Sub-Conn, and Max-Flow require either n^δ−o(1) amortized update or query time, or n^2+δ−o(1) preprocessing.

    Source: §1.1.1 · p. 6

    The real-input reductions are framed for a reasonable restricted Real RAM model, rather than an unrestricted Real RAM.

    Source: §1 · p. 3

Abstract

from arXiv · show

The $3$SUM hypothesis, the APSP hypothesis and SETH are the three main hypotheses in fine-grained complexity. So far, within the area, the first two hypotheses have mainly been about integer inputs in the Word RAM model of computation. The "Real APSP" and "Real $3$SUM" hypotheses, which assert that the APSP and $3$SUM hypotheses hold for real-valued inputs in a reasonable version of the Real RAM model, are even more believable than their integer counterparts. Under the very believable hypothesis that at least one of the Integer $3$SUM hypothesis, Integer APSP hypothesis or SETH is true, Abboud, Vassilevska W. and Yu [STOC 2015] showed that a problem called Triangle Collection requires $n^{3-o(1)}$ time on an $n$-node graph. Our main result is a nontrivial lower bound for a slight generalization of Triangle Collection, called All-Color-Pairs Triangle Collection, under the even more believable hypothesis that at least one of the Real $3$SUM, the Real APSP, and the OV hypotheses is true. Combined with slight modifications of prior reductions, we obtain polynomial conditional lower bounds for problems such as the (static) ST-Max Flow problem and dynamic Max Flow, now under the new weaker hypothesis. Our main result is built on the following two lines of reductions. * Real APSP and Real $3$SUM hardness for the All-Edges Sparse Triangle problem. Prior reductions only worked from the integer variants of these problems. * Real APSP and OV hardness for a variant of the Boolean Matrix Multiplication problem. Along the way we show that Triangle Collection is equivalent to a simpler restricted version of the problem, simplifying prior work. Our techniques also have other interesting implications, such as a super-linear lower bound of Integer All-Numbers $3$SUM based on the Real $3$SUM hypothesis, and a tight lower bound for a string matching problem based on the OV hypothesis.

1 Introduction

Fine-grained complexity uses reductions to relate problems with long-standing running times, while the 3SUM, APSP, and SETH hypotheses support many conditional lower bounds. This introduction asks whether meaningful hardness results can instead rely on weaker assumptions, including hypotheses for real-valued inputs.

1 Introduction

  • Fine-grained reductions relate problems with long-standing running times, and 3SUM, APSP, and CNF-SAT hypotheses underpin many conditional lower bounds.The area takes a problem-centric approach to complexity.Source: §1 · p. 2
  • Under Hypothesis 1, Abboud, Vassilevska W. and Yu proved n^3-o(1) hardness for Triangle Collection, supporting lower bounds for flow and dynamic-graph problems.The cited applications include dynamic maximum flow, #SSR, and #SCC.Source: §1 · pp. 2–3
  • The paper asks whether meaningful lower bounds can follow from weaker assumptions and whether bounds based on integer APSP and 3SUM extend to their real-valued variants.The motivation is that real-valued APSP and 3SUM algorithms are commonly studied, while conditional lower bounds have typically assumed integer inputs.Source: §1 · pp. 2–3
  • Real-3SUM and Real-APSP rule out O(n^2−ε) and O(n^3−ε) algorithms, respectively, for real inputs in a reasonable Real RAM model.The paper characterizes these real-valued hypotheses as more believable than their integer counterparts.Source: §1 · pp. 3–4

1.1 Our results

The paper establishes conditional lower bounds for All-Color-Pairs Triangle Collection under Hypothesis 2: at least one of OVH, Real 3SUM, or Real APSP holds. Its reductions also extend real-input hardness to other problems and relate Triangle Collection to simpler variants.

1.1.1 Main result: hardness for Triangle Collection

  • ACP-Tri-Co requires n^{2+δ−o(1)} time in a reasonable Real RAM model under Hypothesis 2, with the reductions proving δ = 0.25.The result also yields conditional lower bounds for dynamic graph problems and ST-Max-Flow.Source: §1.1.1 · p. 6

1.1.2 Real APSP and Real 3SUM hardness via All-Edges Sparse Triangle

  • AE-Sparse-Tri requires m^{5/4−o(1)} time under Real Exact-Triangle and m^{6/5−o(1)} under Real 3SUM; its counting version requires m^{4/3−o(1)} under Real APSP, Real Exact-Triangle, or Real 3SUM.The reductions use techniques inspired by Fredman’s trick instead of hashing.Source: §1.1.2 · p. 7

1.1.3 Real APSP and OV hardness via Colorful Boolean Matrix Multiplication

  • Colorful-BMM requires n^{3−o(1)} time under OVH, and the reductions also establish Real-APSP and OV hardness for two matrix-product problems.The additional problems are (distinct, =)-Product and (distinct, +)-Product.Source: §1.1.3 · p. 8

1.1.4 Equivalence between variants of Triangle Collection

  • Tri-Colight and restricted Tri-Co* variants are equivalent up to n^{o(1)} factors, and Tri-Co* with small parameters is subcubically equivalent to Tri-Co.Tri-Co* with parameters at most n^ε having a truly subcubic algorithm would imply one for Tri-Co.Source: §1.1.4 · pp. 8–9

1.1.5 Other Reductions

  • For degeneracy O(m^α), AE-Colorful-Sparse-Tri has no ˜O(m^{1+α−ε}) algorithm under Hypothesis 2 when 0 < α ≤ 1/5.Enumerating all triangles gives a ˜O(m^{1+α}) algorithm in this setting.Source: §1.1.5 · p. 9
  • If Int-All-Nums-3SUM has a ˜O(n^{6/5−ε}) algorithm, then Real-All-Nums-3SUM has a truly subquadratic algorithm; an analogous implication links Int-AE-Exact-Tri at ˜O(n^{7/3−ε}) to truly subcubic Real-AE-Exact-Tri.These conditional results relate integer-input algorithms to real-input hypotheses.Source: §1.1.5 · p. 9
  • Pattern-to-text distinct Hamming similarity has a matching ˜O(N^{3/2}) algorithm and N^{3/2−o(1)} lower bound under OVH.The lower bound follows using the reduction from OV to Colorful-BMM.Source: §1.1.3 · p. 8, §1.1.5 · p. 9
  • The paper extends Real-APSP hardness to Set-Disjointness and Set-Intersection, so prior Integer-3SUM-based lower bounds for these problems also have Real-APSP hardness.The prior results include hardness for problems such as Triangle Enumeration and Maximum Cardinality Matching.Source: §1.1.5 · p. 10

1.2 An Illustration of Our Techniques: Reduction from Real-APSP to AE-Sparse-Tri

The reduction turns Real-APSP’s min-plus computation into AE-Sparse-Tri queries using Fredman-style comparisons, randomized search, and dyadic intervals. It gives a near m^4/3 conditional lower bound for AE-Sparse-Tri under Real-APSP.

1.2 An Illustration of Our Techniques: Reduction from Real-APSP to AE-Sparse-Tri

  • Random sampling makes rectangular Real-(min, +)-Product reducible to O~(1) calls to the variant, and recursive search takes O(log d log n) oracle calls with high probability.The method samples half of the candidate indices at each step.Source: §1.2 · pp. 10–11
  • Fredman’s comparison rewrites A[i,k′]+B[k′,j] < A[i,k]+B[k,j] as A[i,k′]−A[i,k] < B[k,j]−B[k′,j], encoded as a triangle using dyadic intervals.The method combines Fredman’s trick with randomized search and dyadic intervals.Source: §1.2 · pp. 10–11
  • Real-(min, +)-Product-Variant reduces to O(d) AE-Sparse-Tri instances, each on a graph with O~(n^2/d + dn) edges.The variant supplies a candidate index k_ij for every matrix entry and seeks a better index.Source: §1.2 · pp. 10–11
  • If AE-Sparse-Tri runs in O~(m^(4/3−ε)) time, Real-APSP runs in O~(n^(3−3ε/2)) time, so the Real-APSP hypothesis gives a near m^4/3 lower bound.The reduction uses Las Vegas randomization; the bound matches known upper bounds when ω = 2.Source: §1.2 · pp. 11–12
  • The Real-3SUM reduction likewise adapts an earlier decision-tree method to an AE-Sparse-Tri oracle, but its conditional bounds are not tight in general.The passage reports tight bounds for some degeneracy values and for the counting variant when ω = 2.Source: §1.2 · p. 12
  • The second reduction line uses Colorful-BMM to connect Real-APSP and OV hardness to ACP-Tri-Co.The authors identify the intermediate problem’s introduction as a main innovation.Source: §1.2 · p. 12

1.3 Paper Organization

The paper moves from problem definitions and hardness reductions to its main theorem, then develops further applications. The organization groups related reductions and applications across sections.

1.3 Paper Organization

  • Sections 2–5 establish preliminaries and hardness for AE-Sparse-Tri, its counting version, and AE-Mono-Tri under real-number hypotheses.The sections cover Real 3SUM, Real APSP, and Real Exact-Triangle hardness as specified for each problem.Source: §1.3 · p. 12
  • Section 6 proves Real-APSP and OV hardness for Colorful-BMM, and Section 7 proves the main theorem using Triangle-Collection variants.Section 7 reduces the earlier problems to those variants and establishes equivalences among them.Source: §1.3 · p. 12
  • Sections 8–9 describe further applications of the paper’s techniques and results.Figure 1 depicts the main reductions, and Table 1 summarizes lower-bound results.Source: §1.3 · p. 12

2 Preliminaries

The preliminaries define the paper’s reduction framework, hardness-source problems, Triangle-Collection variants, and additional graph and matrix problems. They also state a Real-3SUM-based lower bound for AE-Exact-Tri.

2 Preliminaries

  • The prefixes AE- and #AE- distinguish per-edge Boolean answers from per-edge counts of qualifying triangles.These abbreviations are introduced for problems asking whether each edge has a triangle with a specified property.Source: §2 · pp. 12–13

2.1 Fine-Grained Reductions

  • A fine-grained reduction preserves conditional hardness: a sufficiently fast algorithm for the target problem would yield a faster algorithm for the source problem.The paper defines reductions through oracle calls whose total size is bounded relative to the source input.Source: §2.1 · p. 13

2.2 Hard Problems

  • For numeric problems, Int-P denotes integer inputs from ±[n^c], while Real-P denotes real-valued inputs.The section defines 3SUM, All-Nums-3SUM, APSP, (min, +)-Product, and triangle problems as hardness sources.Source: §2.2 · pp. 13–14
  • Real-AE-Exact-Tri requires n^2.5−o(1) time assuming Real-3SUM, via an adapted non-tight reduction.The integer 3SUM and APSP hypotheses imply an n^3−o(1) lower bound for Int-AE-Exact-Tri.Source: §2.2 · p. 15

2.3 Triangle Collection and Variants

  • Tri-Co asks for triangles covering every triple of colors; Tri-Co* restricts graph structure, while Tri-Co** is a special case and Tri-Colight limits each color to p nodes.The section also defines ACP-Tri-Co, which reports for each pair of colors whether triangles exist for every third color.Source: §2.3 · pp. 15–16

2.4 Other Problems

  • AE-Sparse-Tri asks whether each edge lies in a triangle, while AE-Mono-Tri asks whether each edge lies in a monochromatic-edge triangle.For affirmative answers, witness triangles may be required without changing complexity beyond polylogarithmic factors.Source: §2.4 · p. 16
  • Colorful-BMM checks whether the witnesses for each matrix entry cover every color, and AE-Colorful-Sparse-Tri asks whether triangle neighbors of each edge cover every color.Source: §2.4 · p. 16

3 Hardness of All-Edges Sparse Triangle

This section establishes conditional hardness for All-Edges Sparse Triangle from Real-APSP, Real-Exact-Tri, and Real-3SUM, including bounds parameterized by graph degeneracy. It also shows that sufficiently fast algorithms for the problem would yield faster algorithms for Real-3SUM and Real-All-Nums-3SUM.

3 Hardness of All-Edges Sparse Triangle

  • An ˜O(m^(1+α−ε)) AE-Sparse-Tri algorithm for degeneracy ˜O(m^α), α ≤ 1/3, would solve Real-APSP in ˜O(n^(3−2ε/(1+α))) time.This yields the specific implication that an ˜O(m^(4/3−ε)) algorithm would solve Real-APSP in ˜O(n^(3−3ε/2)) time.Source: §3 · p. 17
  • An ˜O(m^(5/4−ε)) AE-Sparse-Tri algorithm would solve Real-Exact-Tri and Real-AE-Exact-Tri in ˜O(n^(3−4ε/3)) time.More generally, for degeneracy ˜O(m^α), α ≤ 1/4, an ˜O(m^(1+α−ε)) algorithm gives a ˜O(n^(3−2ε/(1+2α))) time algorithm for both problems. The reduction uses O(d^2) AE-Sparse-Tri instances with ˜O(n^2/d^2+dn) edges and degeneracy ˜O(d).Source: §3 · pp. 18–19
  • Real-3SUM-Variant2 reduces to one AE-Sparse-Tri instance with ˜O(ˆnn/d+d^2n) edges and degeneracy ˜O(d).The reduction uses Fredman’s trick and yields a tight conditional lower bound when degeneracy is ≪m^1/5; the section treats the asymmetric case with input set sizes n, n, and ˆn ≤ n.Source: §3 · pp. 19–21
  • An ˜O(m^6/5−ε)-time AE-Sparse-Tri algorithm would solve Real-3SUM and Real-All-Nums-3SUM in ˜O(n^2−5ε/3) time with Las Vegas randomization.This is the symmetric case of the reduction, with β = 1.Source: §3 · p. 21
  • For degeneracy ˜O(m^α), an ˜O(m^1+α−ε)-time AE-Sparse-Tri algorithm implies ˜O(n^1+β−ε(1+β)/(1+α))-time Real-3SUM for set sizes n, n, and n^β, when α ≤ β/(3 + 2β).The reduction proceeds through Real-3SUM-Variant1, choosing d = n^((1+β)α/(1+α)) so that d²n ≤ n^(1+β)/d.Source: §3 · p. 21

4 Hardness of All-Edges Sparse Triangle Counting

The paper strengthens counting lower bounds for All-Edges Sparse Triangle by reducing Real-Exact-Tri and Real-3SUM to its counting variant. These reductions yield near-m^4/3 conditional bounds matching the Real-APSP reduction.

4 Hardness of All-Edges Sparse Triangle Counting

  • For counting, the reductions adapt the Real-Exact-Tri and Real-3SUM routes, bringing their conditional lower bounds near m^4/3 to match the Real-APSP reduction.The known O(m^2ω/(ω+1)) algorithm for #AE-Sparse-Tri makes these bounds tight if ω = 2.Source: §4 · p. 21
  • Real-Exact-Tri-Variant3 reduces to O(d) #AE-Sparse-Tri instances with O~(n^2/d + dn) edges and degeneracy O~(d).This route recovers the same result as the Real-APSP reduction by working with single indices rather than pairs.Source: §4 · p. 22
  • If #AE-Sparse-Tri runs in O~(m^4/3−ε), then Real-Exact-Tri and its stated counting variants run in O~(n^3−3ε/2).The reduction uses Las Vegas randomization.Source: §4 · p. 22
  • For degeneracy O~(m^α), α ≤ 1/3, an O~(m^1+α−ε) algorithm for #AE-Sparse-Tri would give O~(n^3−2ε/(1+α)) algorithms for Real-Exact-Tri variants.The variants include Real-#AE-Exact-Tri and Real-#AE-Neg-Tri.Source: §4 · p. 22
  • Real-3SUM-Variant3 reduces to one #AE-Sparse-Tri instance with O~(n^2/d + dn) edges and degeneracy O~(d).The reduction counts qualifying index pairs through triangles in a constructed graph.Source: §4 · pp. 23–24
  • If #AE-Sparse-Tri runs in O~(m^4/3−ε), then Real-3SUM and Real-All-Nums-3SUM run in O~(n^2−3ε/2).The reduction uses Las Vegas randomization.Source: §4 · p. 24
  • For degeneracy O~(m^α), α ≤ 1/3, an O~(m^1+α−ε) algorithm for #AE-Sparse-Tri would give O~(n^2−2ε/(1+α)) algorithms for Real-3SUM variants.The variants include Real-All-Nums-3SUM.Source: §4 · p. 24

5 Hardness of All-Edges Monochromatic Triangle

The paper transfers reductions from Real-APSP, Real-Exact-Tri, and Real-3SUM to All-Edges Monochromatic Triangle. Combining multiple All-Edges Sparse Triangle instances into monochromatic instances yields conditional lower bounds for the monochromatic problem.

5 Hardness of All-Edges Monochromatic Triangle

  • Multiple AE-Sparse-Tri instances reduce to AE-Mono-Tri by overlaying input graphs as an edge-colored graph after randomly permuting their nodes [LPV20].The corresponding counting variants transfer in the same way.Source: §5 · p. 24
  • If AE-Mono-Tri runs in O~(n^5/2−3ε/2), then Real-APSP runs in O~(n^3−ε).More generally, with O~(n^α) colors and α ≤ (1−ε)/2, an O~(n^2+α−ε) algorithm would give the same Real-APSP bound.Source: §5 · p. 24
  • If #AE-Mono-Tri runs in O~(n^5/2−3ε/2), then Real-Exact-Tri and Real-#AE-Exact-Tri run in O~(n^3−ε).The reductions use Las Vegas randomization.Source: §5 · p. 25
  • If AE-Mono-Tri runs in O~(n^7/3−4ε/3), then Real-Exact-Tri runs in O~(n^3−ε).The more general bound uses O~(n^2α) colors, with α ≤ (1−ε)/3, and an O~(n^2+α−ε) algorithm.Source: §5 · p. 25
  • If #AE-Mono-Tri runs in O~(n^5/2−15ε/8), then Real-3SUM runs in O~(n^2−ε).The reduction uses Las Vegas randomization.Source: §5 · p. 26
  • If AE-Mono-Tri runs in O~(n^9/4−45ε/32), then Real-3SUM runs in O~(n^2−ε).The reduction uses Las Vegas randomization.Source: §5 · p. 26

6 Hardness of Colorful BMM

This section reduces Real-APSP and OV to Colorful-BMM, using logical formulations of their computations. It derives conditional running-time consequences for Colorful-BMM algorithms.

6 Hardness of Colorful BMM

  • Real-(min, +)-Product reduces to Colorful-BMM with O(d) colors and inner dimension ˜O(d^4 n^ε), after ˜O(dn^(2−ε)) preprocessing time.Real-APSP is equivalent to Real-(min, +)-Product.Source: §6 · p. 27
  • The Real-APSP reduction encodes bits of the minimizing index using rank comparisons over dyadic intervals, then determines them through Colorful-BMM.The construction handles each bit of arg min_k(A[i,k]+B[k,j]); a high-versus-low degree step reduces the inner dimension.Source: §6 · p. 27
  • A Colorful-BMM algorithm running in ˜O(n^(9/4−5ε/4)) time would give a ˜O(n^(3−ε))-time Real-APSP algorithm.More generally, with O(n^α) colors, a ˜O(n^(2+α−ε))-time algorithm suffices when α ≤ (1−ε)/4.Source: §6 · p. 28
  • One OV instance on n vectors in f dimensions reduces in O(ndf) time to Colorful-BMM matrices of dimensions (n/d) × (d²f) and (d²f) × (n/d), with d² colors.The reduction groups vectors into sets of d and represents their bits in the matrices.Source: §6 · p. 28
  • A ˜O(N^(3−ε))-time algorithm for N × N Colorful-BMM would solve OV in ˜O(f^O(1)n^(2−2ε/3)) time.With N^α colors and running time ˜O(N^(2+α−ε)), the resulting OV time is ˜O(f^O(1)n^(2−2ε/(2+α))) for α ≤ 1.Source: §6 · p. 28

7 Triangle Collection and Triangle-Collection*

The section relates Triangle Collection variants and gives reductions to All-Color-Pairs Triangle Collection from All-Edges Monochromatic Triangle and Colorful-BMM. These reductions support the stated conditional hardness results.

7 Triangle Collection and Triangle-Collection*

  • Original Tri-Co and tripartite-Tri-Co are equivalent, with added nodes and edges ensuring repeated-color triples while preserving triangles for distinct-color triples.The same equivalence holds for their All-Color-Pairs variants.Source: §7 · p. 29
  • Tri-Co*, Tri-Co**, and Tri-Colight are equivalent up to n^o(1) factors when their parameters are n^o(1).Tri-Colight with parameter p reduces in O(n²p³) time to Tri-Co** on O(np³) nodes with parameter p³.Source: §7 · p. 31
  • Tri-Co on n nodes reduces to Tri-Colight with parameter n^ε in n^(3−min{ε,0.3}+o(1)) time.The reduction handles frequent colors using rectangular matrix multiplication and leaves infrequent-color triples in Tri-Colight.Source: §7 · pp. 31–32

7.1 From All-Edges Monochromatic Triangle to All-Color-Pairs Triangle Collection

  • Assuming Hypothesis 2, ACP-Tri-Co requires n^(2+δ−o(1)) time for some δ > 0 in a reasonable Real RAM model.The section connects this result to Real-APSP, Real-3SUM, and OV through reductions.Source: §7 · p. 32
  • An n-node AE-Mono-Tri instance reduces in O(n² log n) time to ACP-Tri-Colight on O(n log n) nodes with parameter O(log n).The construction uses O(log n) graphs, encoding edge-color bits so a color triple lacks a triangle exactly when the three edge colors match in every bit.Source: §7.1 · p. 32
  • Colorful-BMM on n × n matrices reduces in O(n²) time to ACP-Tri-Co; if each color occurs at most n^o(1) times, it reduces to ACP-Tri-Co* with parameter n^o(1).The graph encodes a matrix product entry as a triangle for each relevant color triple.Source: §7.1 · p. 33
  • The section also obtains a reduction from OV to Tri-Co*, beyond the reduction to ACP-Tri-Co.This follows by unrolling the OV-to-Colorful-BMM reduction and the reduction to ACP-Tri-Co.Source: §7.1 · p. 33
  • For any 1 ≤ d ≤ n, OV on n Boolean vectors in f dimensions reduces in O(n²/d² + ndf) time to Tri-Colight on O(nf/d + d²) nodes with parameter f.If OV requires n^(2−o(1)) time for f = n^o(1), then Tri-Colight with parameter N^o(1), and hence Tri-Co* with parameter n^o(1), requires N^(3−o(1)) time.Source: §7.1 · p. 33

8 Other Reductions

This section develops further reductions and applications of conditional hardness, including transfers involving triangle problems, integer problems, string matching, and set queries. In particular, it reduces triangle-listing instances to Set-Intersection, establishing an N^{2-o(1)} lower bound in the stated parameter ranges while outputting only ˜O(n²) triangles with high probability.

8.1 Hardness of AE-Colorful-Sparse-Tri

  • For D ≪ m^1/5, AE-Colorful-Sparse-Tri requires mD time up to n^o(1) under Real APSP, Real 3SUM, or OV, matching triangle enumeration.The bound applies to graphs with m edges and degeneracy D; enumerating all triangles takes O(mD) time.Source: §8.1 · p. 34

8.2 Real-to-Integer Reductions

  • If Int-All-Nums-3SUM runs in ˜O(n^6/5−ε), Real-All-Nums-3SUM runs in ˜O(n^2−5ε/3); likewise, a Real-All-Nums-Convolution-3SUM algorithm in O(n^6/5−ε) implies subquadratic Real-All-Nums-3SUM.The second implication uses known reductions from Int-All-Nums-3SUM to Int-All-Nums-Convolution-3SUM [P˘at10, KPP16, CH20] and the paper’s real-to-integer reduction.Source: §8.2 · p. 34
  • Under Real 3SUM, jumbled indexing cannot have both O(n^1+ασ) preprocessing and O(n^βσ) query time for positive ασ, βσ when σ is a sufficiently large constant.This follows by combining the reduction from Int-All-Nums-3SUM to jumbled indexing by Amir, Chan, Lewenstein, and Lewenstein [ACLL14] with the paper’s real-to-integer reduction; the bound is weaker than [ACLL14]’s.Source: §8.2 · p. 35
  • AE-Mono-Tri with n^α colors reduces to Int-AE-Exact-Tri with weights in ±[n^α+o(1)], yielding conditional n^3−ε+o(1) implications for exact and counting variants.Specifically, an ˜O(n^2+α−ε) algorithm for Int-AE-Exact-Tri with weights in ±[n^2α] would give Real-AE-Exact-Tri in n^3−ε+o(1), for α ≤ (1−ε)/3; analogous bounds hold for exact or negative counting variants with weights in ±[n^α] and α ≤ (1−ε)/2. The reduction encodes colors using a Salem-Spencer set so zero triangles correspond to monochromatic triangles.Source: §8.2 · p. 35

8.3 An Application to String Matching

  • OV reduces to pattern-to-text distinct Hamming similarity: an O(N^3/2−ε) algorithm on length-O(N) strings gives an O(f^O(1)n^2−4ε/3) OV algorithm.More generally, with alphabet size O(N^α), an O(N^1+α−ε) algorithm for α ≤ 1/2 implies an O(f^O(1)n^2−2ε/(1+α)) OV algorithm.Source: §8.3 · pp. 36–37

8.4 Hardness of Set-Disjointness and Set-Intersection from Real-APSP

  • Under Real APSP, Set-Disjointness with |U|=O(N^2−2γ), |F|=O(N), set size O(N^1−γ), and q=O(N^1+γ) has no O(N^2−ε)-time algorithm for 0<γ<1.The reduction yields the same conditional lower bound under the stated parameter restrictions.Source: §8.4 · p. 37
  • Under Real APSP, no O(N^2−ε)-time algorithm can output O(N^2−δ) intersection elements with |U|=O(N^1+δ−γ), |F|=O(N^1+δ+γ), set size O(N^1−γ), and q=O(N^1+γ).The theorem states this for any 0<γ<1 and δ≥0; the section presents it as a matching lower bound for Set-Intersection.Source: §8.4 · p. 38
  • The triangle-listing algorithm outputs only ˜O(n^2) triangles over its full execution with high probability.Source: §8.4 · p. 39
  • The triangle-listing instances can be reduced to Set-Intersection.Source: §8.4 · p. 39
  • The reduction yields an N^{2-o(1)} lower bound when δ + γ ≥ 1 and δ ≤ 2.The parameters also satisfy 2 ≤ t and td ≤ n^2.Source: §8.4 · p. 39

9 Miscellaneous Remarks

The section extends the paper’s hardness results to variants of Boolean matrix multiplication and equality products, and derives a conditional lower bound for AE-Sparse-Tri from Real-(2k+1)SUM.

9 Miscellaneous Remarks

  • Real-APSP and OV hardness reductions extend to Mode-BMM, which returns the most frequent color among matching indices.The same approach relates Colorful-BMM and Mode-BMM to equality matrix products, yielding near-cubic lower bounds under OVH.Source: §9 · p. 40
  • Colorful-BMM and Mode-BMM reduce to the corresponding distinct-equality and mode-equality products, with nearly matching OVH-based lower bounds for bounded integer entries.For entries bounded by n^α, the products have ˜O(n^(2+α+o(1))) algorithms when ω = 2; the stated nearly matching lower bounds apply for α ≤ 1.Source: §9 · p. 40
  • An ˜O(m^(1+α−ε)) algorithm for AE-Sparse-Tri at α ≤ 1/(3k+2) would yield an ˜O(n^(k+1−ε(k+1)/(1+α))) algorithm for Real-(2k+1)SUM.The implication holds for any fixed k and uses Las Vegas randomization.Source: §9 · p. 40
  • Adapting the reduction to certain algebraic 3SUM generalizations appears possible using more advanced geometric range searching, but the resulting bounds would be worse.The cited generalizations ask whether f(a,b)=c for a fixed constant-degree bivariate polynomial f.Source: §9 · p. 40

A Model of Computation

The section specifies Real RAM models intended to keep real-input reductions meaningful while controlling computational power. It also derives a Real-3SUM-based lower bound for Real-Exact-Tri and discusses implications for large-integer inputs.

A Model of Computation

  • The proposed Real RAM models retain Word RAM operations while restricting real-number operations; the weakest model allows only 4-linear comparisons.These restricted models are presented as sufficient for the reductions and as more believable bases for conditional lower bounds.Source: A Model of Computation · p. 46
  • The Real-APSP model restricts intermediate registers to path lengths, preventing repeated doubling and exponentially large register values.The passage describes this as a requirement on register values and allows comparisons between sums of register values.Source: A Model of Computation · p. 47
  • For low-degree computation, restricting register values to constant-degree polynomials supports Word RAM simulation for integer inputs, with a subpolynomial slowdown under relaxed degree and coefficient bounds.The relaxed model allows degree n^o(1) and coefficients bounded by 2^(n^o(1)).Source: A Model of Computation · p. 47
  • Some Real RAM algorithms fall outside the stronger models because they generate intermediate numbers iteratively through deep trees; the paper describes such examples as generally impractical due to precision issues.The example given is minimum-link paths in polygons.Source: A Model of Computation · p. 47
  • Unrestricted Real RAM operations can substantially change complexity: arithmetic with floor can solve PSPACE-hard problems in polynomial time, and additions can provide a polynomial advantage over Word RAM.The paper also notes unusual near-linear sparse-triangle detection and fast Int-APSP algorithms in an unrestricted model without floor.Source: A Model of Computation · pp. 46–48
  • For any fixed δ > 0, an ˜O(m^(4/3−ε)) AE-Sparse-Tri algorithm would give truly subcubic Int-APSP for O(n^(1/2−δ))-bit integers.The reduction uses ˜O(n^(5/2)) comparisons and restricted additions; the paper says prior Int-APSP reductions handle only n^o(1)-bit integers. Hashing already handles Int-3SUM, but not certain inequality variants directly.Source: A Model of Computation · p. 48
  • Real-Exact-Tri requires n^(2.5−o(1)) time under the Real 3SUM hypothesis; the bucket reduction shows that a truly faster algorithm would imply truly subquadratic Real-3SUM.It creates n^(ε+1/3) instances with n^(2/3) nodes and chooses ε = δ/2 to contradict the hypothesis.Source: A Model of Computation · p. 48
  • The reduction sorts inputs into buckets, identifies O(g^2) valid bucket triples, and encodes candidate element triples as exact triangles.For remaining bucket pairs, each generated instance has three node parts representing buckets and element pairs; an exact triangle corresponds to a Real-3SUM solution.Source: A Model of Computation · p. 48
Loading 2203.08356v2…