PaperlayerView exact revision on arXiv

Source-linked AI summary

Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs

Josh Alman, Virginia Vassilevska Williams

arXiv:2610.06783v1cs.DScs.CC

TL;DR

The paper addresses long-standing limits in 3SUM and sparse-output triangle computation, where standard methods had seen little progress. It introduces an algorithm for lopsided sparse triangle instances and reports polynomial-time improvements for 3SUM and APSP.

  • Problem

    3SUM’s O(n^2) textbook algorithm had seen only polylogarithmic speedups, while sparse-output triangle instances appeared to resist matrix-multiplication techniques.

    Source: §1 · pp. 2, 4

  • Method

    A new algorithm computes a prescribed sparse set of entries in a thin matrix product, directly solving lopsided All-Edges Sparse Triangle instances.

    Source: §1 · p. 4, §2.4.4 · p. 29

  • Results

    Deterministic algorithms solve 3SUM on polynomial-size integers in O(n^1.9992) time and APSP with polynomially bounded integer weights in O(n^2.9995) time.

    Source: §1 · p. 4

  • Takeaways & Limitations

    Known reductions can turn the lopsided triangle algorithm into algorithms for other problems when their reductions produce such instances.

    Source: §1 · p. 4

    The algorithms are algebraic and potentially impractical because their hidden constants are enormous.

    Source: §1.2 · p. 12

Abstract

from arXiv · show

We give the first polynomial improvements over the textbook algorithms for $3$SUM and All-Pairs Shortest Paths (APSP): we show how to deterministically solve $3$SUM on $n$ integers of polynomial size in $O(n^{1.9992})$ time and APSP on directed $n$-vertex graphs with polynomially bounded integer weights in $O(n^{2.9995})$ time. This refutes the $3$SUM and APSP hypotheses. Using known reductions, we also refute the real-valued versions of the $3$SUM and APSP hypotheses, the Exact Triangle hypothesis, the Zero-Weight $k$-Clique hypotheses, and the three rectangular hinted Online Matrix--Vector conjectures of van den Brand, Nanongkai, and Saranurak, and we give polynomial speedups for a variety of other problems. All of these results follow from a single new algorithm for thin matrix products. Let $X$ be an $N\times D$ integer matrix and $Y$ a $D\times N$ integer matrix with $D\le N^{1/18}$, and let $W$ be any set of at most $N^2/\sqrt D$ positions. We compute the entries $(XY)[I,J]$, $(I,J)\in W$, in $O(N^2/D^{0.063})$ operations, which is polynomially less than the time needed to write down $XY$ or to compute $N^2/\sqrt D$ inner products one by one. We design this algorithm by modifying a variant of Coppersmith's rectangular matrix multiplication algorithm, built from a ten-multiplication identity of Sch\"onhage, to perform only the operations needed for the entries in $W$, and show that few operations are needed. Interpreted as a graph algorithm, this solves the All-Edges Sparse Triangle problem in truly subquadratic time on sparse lopsided tripartite graphs where two parts have $n$ vertices but one part has $n^{\varepsilon}$ vertices for $\varepsilon<0.12$. By known reductions, Exact Triangle, and hence $3$SUM and APSP, reduce to this problem. We also give a data structure version that answers queries for single entries of $XY$, not known in advance.

1 Introduction

The section presents a thin-matrix-product algorithm and explains how known reductions extend it to faster algorithms for lopsided All-Edges Sparse Triangle and problems in the 3SUM, APSP, and (min, +)-convolution classes. It also identifies conjectures, parameter regimes, and algorithmic models that the results do not settle.

1 Introduction

  • Deterministic algorithms achieve O(n^1.9992) for polynomial-size integer 3SUM and O(n^2.9995) for APSP with polynomially bounded integer weights.Source: §1 · p. 4
  • The work also improves directed unweighted APSP, Tree Edit Distance, and Online Set Disjointness, while leaving CNF-SAT and Orthogonal Vectors outside its faster-algorithm results.Source: §1 · pp. 4–5

1.1 All-Edges Sparse Triangle

  • For a thin N × D by D × N product, wanted entries are computed deterministically in O(N^2/D^0.063) operations on O(log N)-bit integers; more generally, D ≤ N^ε and |W| ≤ N^2/D^κ yield O(N^2/D^γ), for ε < 0.1204 and κ > 0.Source: §1.1 · p. 5

1.2 Known reductions

  • A deterministic reduction from Exact Triangle to lopsided All-Edges Sparse Triangle, together with randomized reductions for real-valued problems, transfers the triangle algorithm’s speedups to these hypotheses.The real-valued reductions use the counting version of lopsided triangle, and yield Las Vegas algorithms.Source: §1.2 · p. 6
  • Integer algorithms solve Exact Triangle in O(n^2.9983), while Las Vegas algorithms solve real-input 3SUM in O(n^1.998) expected time and real-input APSP and Exact Triangle in O(n^2.998) expected time.The real-valued results use only comparisons, additions, and subtractions on real numbers.Source: §1.2 · p. 7
  • The thin-product algorithm yields deterministic preprocessing in O(N^2/D^0.063) and O(D^0.437)-time queries for individual entries of XY.More generally, for D ≤ N^ε with ε < 0.1204, preprocessing takes O(N^2/D^γ) time and each query takes O(D^q) time for suitable γ > 0.Source: §1.2 · p. 7
  • For t=n^τ with 0<τ<1/18, the data structure refutes all three hinted OMv conjectures, with smaller savings persisting to τ<0.1204.After the hint, the v-hinted Mv algorithm takes O(n^2−0.063τ) time and after the vector O(n^1+0.437τ), improving on the conjectured n^2−o(1) and n^1+τ−o(1) bounds; the uMv result applies when τ1<τ2/18.Source: §1.2 · p. 8
  • The refutation weakens conditional lower bounds for the fastest-query ends of dynamic matrix-inverse trade-offs, partially dynamic distance oracles, and dynamic attention, but not bounds using τ≈0.53.The affected lower bounds had supported conditional optimality for dynamic matrix-inverse algorithms of Sankowski and van den Brand et al. [vdBNS19].Source: §1.2 · p. 8
  • The reductions yield the first truly subcubic algorithms for problems in the APSP class, including Diameter and many problems reducible to APSP but not known to be equivalent.The paper also lists Negative Triangle, Minimum Weight Cycle, Replacement Paths, Second Shortest Simple Path, Radius, Median, Betweenness Centrality, Metricity, Tree Edit Distance, Maximum Subarray, and the Wiener Index.Source: §1.2 · pp. 8, 10
  • The paper gives the first truly subquadratic algorithms for listed problems in the 3SUM equivalence class, and an O(n^1.4999)-time algorithm for MonoConvolution.The class includes All-Numbers 3SUM, Convolution-3SUM, and nontrivial 3-Linear Degeneracy Testing variants such as 3AP; MonoConvolution’s prior bound was ˜O(n^1.5) [LPV20].Source: §1.2 · p. 10
  • The results give the first truly subquadratic algorithms for (min, +)-convolution-equivalent problems and refute the (min, +)-convolution hypothesis.They also give first ˜O(n+t^2−δ)-time algorithms for 0/1 and Unbounded Knapsack and a ˜O(n+(1/ε)^2−δ)-time approximation scheme for Subset Sum, for constant δ>0; only the Unbounded Knapsack algorithm is deterministic.Source: §1.2 · p. 10
  • The Exact Triangle algorithm gives O(n^k−ε)-time algorithms for zero-, min-, and max-weight k-Clique for constant k≥3, refuting their hypotheses [AL13] [LVW18] [BDT16].Source: §1.2 · p. 11
  • The same approach gives the first truly subquadratic algorithm for 3XOR and first truly subcubic algorithms for #Exact Triangle and counting witnesses of the (min, +)-product, plus a truly subquadratic algorithm for #3SUM.3XOR is not known to reduce to 3SUM; the counting-version equivalences are stated in [CVX23], with deterministic equivalence for #3SUM in [FJX25].Source: §1.2 · p. 11
  • For problems known only to be 3SUM-hard or APSP-hard, the results give no faster algorithms because reductions go the other way; finding three collinear points among n planar points remains open in truly subquadratic time.For k-SUM with k ≥ 4, they obtain no polynomial improvement, and the reductions yield algorithms far slower than the n⌈k/2⌉ baseline.Source: §1.2 · pp. 11–12

2 Quickly computing certain entries of a thin matrix product

The paper’s main algorithm computes a prescribed sparse set of entries of a thin matrix product in subquadratic time by pruning a recursive multiplication procedure. Its bounds apply to arbitrary dense inputs and wanted positions subject to stated size and dimension constraints.

2 Quickly computing certain entries of a thin matrix product

  • O(N^2 log^2D/D^1/18) time computes any wanted set of at most N^2/D entries when D is a power of four and N ≥ D^18.The input matrices have dimensions N×D and D×N, with integer entries of absolute value at most N^O(1).Source: §2 · p. 13
  • The inputs and product may be arbitrary dense matrices, and the wanted set needs no structure beyond its size bound.The section notes that the exponent 18 simplifies the presentation; a later data-structure version improves parameter trade-offs.Source: §2 · p. 13
  • The algorithm visits only recursion-tree leaves needed by wanted outputs, bounding their union to about N^2/D^1/18 leaves for N^2/D wanted entries.It pays O(log^2D) operations per leaf.Source: §2 · p. 14
  • The method modifies Coppersmith’s rectangular multiplication algorithm based on Sch¨onhage’s identity, sharing input-only encodings and pruning calls for unneeded outputs.The encoding additions depend on X alone or Y alone, so they can be reused across calls; N ≥ D^18 helps keep their total cost negligible.Source: §2 · pp. 13–14

2.1 Strassen’s recursive algorithm

Strassen’s algorithm recursively multiplies matrices by replacing the eight scalar products of a 2×2 multiplication with seven products of linear combinations. The recursion has N^log2(7) leaf multiplications, while its additions increase the running time only by a constant factor.

2.1 Strassen’s recursive algorithm

  • Seven products of linear combinations of the entries of two 2×2 matrices suffice to compute their product, instead of eight.Each output entry is then a linear combination of those seven products.Source: §2.1 · p. 14
  • For N = 2^L, the recursive algorithm has 7^L = N^log2(7) leaf multiplications.At each level it forms seven pairs of block linear combinations, recursively multiplies each pair, and assembles the resulting four blocks.Source: §2.1 · p. 14
  • The additions and subtractions across the recursion tree increase the running time by only a constant factor.Their total is O(7^L), a geometric series dominated by its last term.Source: §2.1 · p. 15

2.2 Sch¨onhage’s identity for an inner product and an outer product

Sch¨onhage’s identity computes an outer product and an inner product on disjoint variable sets using ten multiplications rather than thirteen. Its error terms and output-variable structure are useful for the paper’s later sparse-output algorithm.

2.2 Sch¨onhage’s identity for an inner product and an outer product

  • Sch¨onhage’s identity computes the nine outer-product values and the inner-product value using ten multiplications rather than thirteen.The separately computed products would require 9 + 4 = 13 multiplications.Source: §2.2 · p. 16
  • The identity’s polynomial equals the desired outer- and inner-product terms plus an error polynomial whose monomials mix inner inputs with outer outputs.The paper states that this error is harmless in its algorithm.Source: §2.2 · pp. 16–17
  • Every term contributes to z0, while only Pij contributes to zij, a pattern the paper uses to reduce products for sparse wanted outputs.The coefficient for each output variable is the sum of φλψλ over terms contributing to that variable.Source: §2.2 · p. 17

2.3 Rectangular matrix multiplication using Sch¨onhage’s identity

The section recursively applies Sch¨onhage’s identity to obtain rectangular matrix multiplication while retaining structural information about the computation. It explains the recursion, its output as a sum over leaves, and how it batches independent thin products and tiles a larger product.

2.3 Rectangular matrix multiplication using Sch¨onhage’s identity

  • At L recursive levels, choosing inner or outer products yields 2^L matrix products, including products of shape 3^(L−m)×4^m by 4^m×3^(L−m).The section focuses on m much smaller than L so these are thin products.Source: §2.3.1 · p. 17, §2.3 · p. 17

2.3.1 The recursion

  • Full recursively applies the ten terms of Sch¨onhage’s identity, using 10^L leaf multiplications and O(L·10^L) total operations.For L = 1, encoding evaluates the linear forms and decoding assembles the ten outputs.Source: §2.3.1 · p. 18

2.3.2 Unraveling the recursion computation

  • Full(a, b) returns Mult(a, b), whose output string w is the sum of leaf products that contribute to w.The paper uses the leaf-sum description both to read matrix products from Mult and to skip leaves irrelevant to wanted entries.Source: §2.3.2 · pp. 19–20

2.3.3 Batch computation of multiple matrix products

  • One run of Full computes K independent products XQYQ; tiling X by row blocks and Y by column blocks lets runs cover the larger product XY.Tiling enlarges only the outer dimensions, and each block product is a single output of a single Full run.Source: §2.3.3 · pp. 22–23

2.4 Extracting only the desired entries

The algorithm computes only W-indexed product entries by sharing per-band encodings and pruning recursive work to outputs needed by W; its cost hinges on bounding the union of contributing leaves.

2.4.1 Sharing the encoding

  • Each row-band and column-band encoding is computed once and shared across tiles, avoiding the cost of encoding every tile separately.The assumption N ≥ D^18 makes the encoding cost negligible in the final bound.Source: §2.4.1 · p. 24

2.4.2 Skipping the calls that are not needed

  • Pruned skips recursive calls with no wanted outputs, visits exactly the leaves contributing to the requested strings, and runs in time governed by their union.For a set U, the total size of sets passed to calls is at most (L + 1)|Leaves(U)|.Source: §2.4.2 · p. 25

2.4.3 Few leaves contribute to a sparse set of entries

  • The leaf count exploits sharing: higher-order leaves contribute to more output strings, while their total number decreases geometrically.Lemma 11 bounds the union of contributing leaves by summing the smaller of |U|α_d and β_d over orders d.Source: §2.4.3 · pp. 26–27

2.4.4 Proof of Theorem 5

  • For each tile containing wanted positions, the algorithm runs Pruned on their output strings and reports those values, with encoding and recursion costs summed across tiles.Each Pruned call costs O(L|S|); the recursion uses O(log^2D) operations per contributing leaf.Source: §2.4.4 · p. 29
  • O(N^2 log^2D / D^1/18) operations suffice overall, while each tile reaches only O(M/D^1/18) leaves for M wanted entries.The leaf bound is a factor D^1/18 below the tile's M output entries and below the M·D direct inner-product cost.Source: §2.4.3 · p. 28, §2.4.4 · p. 29

3 Exact Triangle reduces to computing certain entries of a thin matrix product

This section connects thin-matrix-product computation to Exact Triangle through a lopsided sparse-triangle problem and a deterministic reduction. It then uses the resulting Exact Triangle algorithm to derive deterministic polynomial speedups for 3SUM, APSP, and 3XOR.

3 Exact Triangle reduces to computing certain entries of a thin matrix product

  • The section derives deterministic Exact Triangle, 3SUM, and APSP algorithms from the matrix theorem, modifying the Exact Triangle-to-lopsided-triangle reduction while the 3SUM and APSP reductions are already deterministic.The construction adapts known instance and witness methods [CX24] and uses deterministic false-positive counting as in [FKP24].Source: §3 · pp. 29–30

3.1 The Lopsided All-Edges Sparse Triangle problem

  • For n ≥ D^18, an instance of #Lop-AE-SparseTri(n, D) or Lop-AE-SparseTri(n, D) with |W| query pairs can be solved deterministically in O(|W| D^0.437 + n^2/D^0.063) time.Source: §3.1 · p. 32

3.2 A deterministic reduction from Exact Triangle to Lop-AE-SparseTri

  • For 16≤D≤n and integer 1≤g≤√D, Exact Triangle reduces deterministically to at most 4ng Lop-AE-SparseTri(n,D) instances.Each instance has at most n^2/D query pairs; the additional time is O(ν n^3 log n/g + n^(ω+o(1))D^(3/2) + n^2Dg), and the reduction is non-adaptive. It hashes weights modulo a deterministically chosen prime by counting false positives, then constructs instances and searches for witnesses.Source: §3.2 · pp. 33–34

3.3 Exact Triangle in truly subcubic time

  • Exact Triangle runs deterministically in O(n^(3−1/648) log^2 n) time, or O(n^(3−0.00175) log n) ≤ O(n^(3−0.0017)) using the stronger matrix-product corollary.These bounds apply to integer weights of absolute value at most n^ν for every constant ν ≥ 1.Source: §3.3 · p. 35
  • Theorem 19 gives Exact Triangle time O(n^(3−ε′) log n), with ε′ = 0.00175, using Corollary 26’s D^0.063 per-instance saving.The reduction balances instance costs and scans with g = ⌈D^0.0315⌉; the exponent improvement is constrained by D^18 ≤ n.Source: §3.4 · p. 35, §3.3 · p. 35

3.4 3SUM and APSP reduce to Exact Triangle

  • Known deterministic reductions map 3SUM to Exact Triangle and use Exact Triangle time T(s) for APSP in O(n^2 T(n^(1/3)) log^3 n).For 3SUM, n integers bounded by n^ν reduce in n^(3/2+o(1)) time to n^(1/2+o(1)) instances on n^(1/2+o(1)) vertices per part.Source: §3.4 · p. 36
  • 3SUM runs in n^(2−1/1296+o(1)) ≤ O(n^1.99923), while min-plus product and APSP run in ~O(n^(3−1/1944)) ≤ O(n^2.99949) deterministically.Using Corollary 26 instead gives 3SUM time n^(2−ε′/2+o(1)) ≤ O(n^1.9992) and min-plus product and APSP time ~O(n^(3−ε′/3)) ≤ O(n^2.99942).Source: §3.4 · p. 36
  • The same approach yields a deterministic truly subquadratic algorithm for 3XOR, using conditional expectations to choose rows of linear hash functions over F2 from an ε-biased set [AGHP92].The problem is to find one vector from each of three lists whose XOR is zero.Source: §3.4 · p. 36

4 The matrix theorem in general: a data structure

This section develops a deterministic data structure for answering individual matrix-product-entry queries, using shared precomputed boxes to summarize leaves. It generalizes the parameters to trade preprocessing and query costs against product thinness and wanted-entry density, yielding explicit bounds for sparse outputs.

4 The matrix theorem in general: a data structure

  • The switching order trades query time against preprocessing, while the ratio c = L/m trades time savings against how thin the product must be; the technique reaches D ≤ N^0.1204.The section states that larger c reduces the box rate but increases encoding size relative to D, requiring N to be a larger power of D for encoding time to fit the bound.Source: §4 · p. 39

4.1 The results

  • For every ε < 0.1204 and κ > 0, Theorem 25 computes up to N^2/D^κ specified entries in O(N^2 log^2 D / D^γ) time for some γ > 0.It applies to matrices with 2 ≤ D ≤ N^ε and entries bounded in absolute value by N^O(1).Source: §4.1 · p. 39
  • When N ≥ D^18, Corollary 26 gives O(N^2/D^0.063) preprocessing and O(D^0.437) per query, or O(|W| D^0.437 + N^2/D^0.063) for wanted entries.The per-query and total wanted-entry bounds are deterministic; the total time is O(N^2/D^0.063) whenever the query term is no larger than that preprocessing term.Source: §4.1 · p. 40

4.2 Boxes

  • Queries read leaves below a switching order directly and sum precomputed boxes for higher-order leaves; each output entry’s higher-order leaves are partitioned exactly once among α_t boxes.Boxes are shared across output entries, and dynamic programming computes their values from smaller boxes.Source: §4 · p. 39, §4.2 · pp. 40, 44
  • Boxes partition the contributing leaves of order at least t: each such leaf belongs to exactly one box, and the boxes cover leaves of orders t through m.This lets the query aggregate higher-order contributions through stored box values.Source: §4.2 · p. 44

4.3 The data structure, in terms of the parameters

  • The structure shares row- and column-band encodings across tiles, stores each tile’s box values, and answers a query by summing encoded leaf products and box values.The resulting sum is the requested entry (XY)[I,J].Source: §4.3 · pp. 45, 47

4.4 Choosing the parameters

  • For L = 21m and t = ⌈m/9⌉, preprocessing takes O(N^2/D^0.063) time and space, while a query takes O(D^0.437) time.The proof first obtains O(m^2N^2/D^γ) preprocessing and O(mD^q) query bounds, then absorbs the logarithmic factors.Source: §4.4 · p. 48
  • As c decreases to 10, R_c(0) increases to ε* = ln 4/(5 ln 10) = 0.1204....This is the limiting exponent stated for the parameterized bounds.Source: §4.4 · p. 49
  • For |W| ≤ N^2/D^κ, the method saves a factor D^min{γ,κ−q}, up to logarithmic factors, over computing the full product.The entries at positions in W are computed deterministically under the parameter conditions of Corollary 31.Source: §4.4 · p. 49

5 Further reductions

This section extends the thin-product and sparse-triangle algorithms, along with the real-input comparison-count method, through further reductions to additional problems. It covers speedups for APSP and real-valued problems, applications to weighted k-Clique and thin hinted matrix-vector conjectures, and which dynamic-algorithm lower bounds are affected or remain supported.

5 Further reductions

  • For n ≥ D^18, Lop-AE-SparseTri and its counting version run deterministically in O(|W|D^0.437 + n^2/D^0.063), and Exact Triangle reduces to Lop-AE-SparseTri.The thin-product data structure preprocesses in O(N^2/D^0.063) time and answers each product-entry query in O(D^0.437) time.Source: §5 · p. 50

5.1 Directed APSP with small integer weights

  • Directed unweighted APSP, and directed APSP with polylogarithmically bounded integer weights and no negative cycles, has a deterministic O(n^(2+µ−ε'') )-time algorithm.The reduction derandomizes Zwick’s algorithm using hierarchical bridging sets and computes distances to and from small vertex sets.Source: §5.1 · pp. 51, 53

5.2 3SUM, APSP, and Exact Triangle with real inputs

  • 3SUM runs in O(n^1.998) expected time, while real (min, +)-product, APSP, and Exact Triangle run in O(n^2.998) expected time, with success probability at least 1 − n^-c.These are Las Vegas algorithms in a real RAM using comparisons, additions, and subtractions.Source: §5.2 · p. 54
  • The real-input reductions of [CVX22] convert their counting problems into comparison counts, which Fredman’s trick reduces to wanted entries of a thin matrix product.Only the [CVX22] reduction steps are randomized; the resulting algorithms never output a wrong answer and are Las Vegas.Source: §5.2 · p. 54
  • Real-input comparison counts can be computed deterministically using only comparisons, yielding expected 3SUM time ˜O(n^1.9979) and ˜O(n^2.975) additional time for the min-plus/APSP/Exact Triangle counting-call application.The comparison-count algorithm handles both < and ≤; the randomized reductions give always-correct output, with high-probability running-time bounds.Source: §5.2 · pp. 57–58

5.3 Zero-Weight, Min-Weight, and Max-Weight k-Clique

  • For constant k ≥ 3 and ν ≥ 1, zero-weight decision and minimum- or maximum-weight k-Clique on complete k-partite graphs take O(n^(k−εT⌊k/3⌋)) time, refuting the corresponding hypotheses even on general graphs.The reduction uses Exact Triangle instances with n^⌊k/3⌋ vertices per part; the extension to general graphs uses the standard reduction to complete k-partite form.Source: §5.3 · pp. 58–59

5.4 Three conjectures of van den Brand, Nanongkai, and Saranurak

  • For 0 < τ < 1/18, hinted OMv conjectures 5.2 and 5.7 fail with Phase 2 time O(n^(2−0.063τ)) and Phase 3 time O(n^(1+0.437τ)); Conjecture 5.12 also fails when 0 < τ1 < τ2/18.For Conjecture 5.12, Phase 3 takes O(n^(1+τ2−0.063τ1)) and Phase 4 takes O(n^(τ2+0.437τ1)), with polynomial Phase 1 and Phase 2 only storing I.Source: §5.4 · p. 59
  • The failures extend to τ < ε* = 0.1204... for Conjectures 5.2 and 5.7, and τ1 < ε*τ2 for Conjecture 5.12, independent of ω.The cited conjectures are those of van den Brand, Nanongkai, and Saranurak [vdBNS19].Source: §5.4 · p. 59
  • For τ < 0.1204, the refuted conjecture forms no longer support the fastest-query dynamic trade-offs, while the main bounds at τ ≈ 0.53 and τ1 + τ2 ≈ 1.41 remain supported by unrefuted regimes.The proof also applies to a variant of Conjecture 5.7 where Phase 2 supplies a matrix with at most n^τ nonzero entries, so that variant cannot support the cited dynamic-attention lower bound for τ < 0.1204.Source: §5.4 · pp. 60–61

6 Conclusion

The paper highlights fine-grained reductions as tools for algorithm design as well as conditional hardness, while identifying open questions about which hypotheses remain useful. It also points to limits and opportunities in extending the lopsided sparse-triangle and thin-matrix-product speedups.

6 Conclusion

  • The lopsided All-Edges Sparse Triangle algorithms do not speed up the balanced case, whose m^(4/3−o(1)) hypothesis remains a potential source of hardness evidence.The balanced case is the target of several lower-bound reductions from 3SUM and Exact Triangle.Source: §6 · p. 61
  • Many problems known only to be 3SUM-hard or APSP-hard remain open for faster algorithms because the reductions go in the opposite direction.The passage also asks whether ideas like these could help on problems such as deciding whether three planar points are collinear.Source: §6 · p. 61
  • The paper’s technique addresses sparsity at least in lopsided instances, but does not appear to yield new sparse matrix multiplication algorithms.The authors relate the open question of improving sparse matrix multiplication to the balanced All-Edges Sparse Triangle problem.Source: §6 · p. 61
  • The reductions from Exact Triangle to Lopsided All-Edges Sparse Triangle keep half the exponent saving, while those from 3SUM and APSP to Exact Triangle keep a half and a third.These reductions were designed to establish hardness, where retaining some polynomial saving suffices; how much they retain matters when used algorithmically.Source: §6 · pp. 61–62
  • A different technique might improve exponents, yield combinatorial or practical algorithms, or handle All-Edges Sparse Triangle instances with a middle part larger than n^0.12.An example is a middle part of size n^1/2, which arises in an approach to girth approximation.Source: §6 · p. 62
  • The authors do not know the true complexity of computing selected entries of a thin matrix product and identify Schӧnhage-identity properties as central to their analysis.The analysis uses the identity’s sparsity and the sharing of recursion leaves among output entries; it is unclear how other tensors could be used similarly.Source: §6 · p. 62
Loading 2610.06783v1…