Source-linked AI summary
Monochromatic Triangles, Intermediate Matrix Products, and Convolutions
Andrea Lincoln, Adam Polak, Virginia Vassilevska Williams
TL;DR
The paper addresses whether fine-grained reductions can explain the intermediate runtimes of matrix, graph, and convolution problems. It develops reductions among these problems and relates MonoConvolution to 3SUM, while the CoinChange reduction is no longer tight against current best known running times.
Problem
The distance product and APSP have only mildly subcubic known algorithms, unlike the faster Max-Min product, raising questions about the complexity of intermediate problems.
Source: §1 · p. 2Method
The paper develops fine-grained reductions among matrix, graph, and convolution problems, including reductions connecting MonoConvolution and 3SUM.
Source: Reductions for Convolution Problems · p. 5, §3 · pp. 8, 11Results
MonoConvolution is fine-grained equivalent to 3SUM, relating natural problems with different running-time complexities.
Source: Reductions for Convolution Problems · p. 5, §4 · pp. 12–13Takeaways & Limitations
The equivalence provides a fine-grained connection between intermediate convolution and 3SUM, while reductions also connect APSP and Minimum Witness to intermediate problems.
Source: Reductions for Convolution Problems · p. 5The CoinChange reduction is no longer tight against the best currently known running times after a faster algorithm by Chan and He.
Source: Reductions for Convolution Problems · p. 6
Abstract
from arXiv · showhide
The most studied linear algebraic operation, matrix multiplication, has surprisingly fast $O(n^\omega)$ time algorithms for $\omega<2.373$. On the other hand, the $(\min,+)$ matrix product which is at the heart of many fundamental graph problems such as APSP, has received only minor improvements over its brute-force cubic running time and is widely conjectured to require $n^{3-o(1)}$ time. There is a plethora of matrix products and graph problems whose complexity seems to lie in the middle of these two problems. For instance, the Min-Max matrix product, the Minimum Witness matrix product, APSP in directed unweighted graphs and determining whether an edge-colored graph contains a monochromatic triangle, can all be solved in $\tilde O(n^{(3+\omega)/2})$ time. A similar phenomenon occurs for convolution problems, where analogous intermediate problems can be solved in $\tilde O(n^{1.5})$ time. Can one improve upon the running times for these intermediate problems, in either the matrix product or the convolution world? Or, alternatively, can one relate these problems to each other and to other key problems in a meaningful way? This paper makes progress on these questions by providing a network of fine-grained reductions. We show for instance that APSP in directed unweighted graphs and Minimum Witness product can be reduced to both the Min-Max product and a variant of the monochromatic triangle problem. We also show that a natural convolution variant of monochromatic triangle is fine-grained equivalent to the famous 3SUM problem. As this variant is solvable in $O(n^{1.5})$ time and 3SUM is in $O(n^2)$ time (and is conjectured to require $n^{2-o(1)}$ time), our result gives the first fine-grained equivalence between natural problems of different running times.
1 Introduction
The introduction frames intermediate matrix and graph problems between fast matrix multiplication and the much harder distance product, then asks whether fine-grained reductions can explain their runtimes. The paper contributes reductions connecting these problems and convolution variants to each other and to 3SUM.
1 Introduction
- The distance product and APSP have only mildly subcubic known algorithms, while Max-Min admits a substantially faster-than-cubic algorithm through normal matrix multiplication.The paper presents this contrast as evidence of a distinct complexity difference between APSP and all-pairs bottleneck paths.Source: §1 · p. 2
- Several matrix and graph problems have intermediate runtimes, with exponents averaging the brute-force and fast matrix multiplication exponents.The introduction lists Dominance and Equality products, All-Pairs Nondecreasing Paths, and the Minimum Witness product and directed unweighted APSP.Source: §1 · p. 2
- The paper asks whether the 2.5 exponent when ω = 2 is coincidental or can be explained by fine-grained reductions among these problems.Earlier known reductions covered only limited pairs, leaving the broader question open.Source: §1 · p. 3
1.1 Our contributions
- The authors reduce Minimum Witness product and directed unweighted APSP to AE-MonoΔ with polylogarithmic overhead.When ω = 2, the reductions transfer any improvement over AE-MonoΔ’s 2.5 exponent to both problems.Source: §1.1 · pp. 4–5
- Directed unweighted APSP also reduces to Min-Max, making Min-Max at least as hard as both it and Minimum Witness product.The stated reduction incurs an O(log n) factor in the running time.Source: §1.1 · p. 5
Reductions for Convolution Problems.
- MonoConvolution is fine-grained equivalent to 3SUM, linking natural problems with different running-time exponents.The paper also reduces CoinChange to MonoConvolution with polylogarithmic overhead, but that reduction is no longer tight against the best currently known running times.Source: Reductions for Convolution Problems · pp. 5–6
2 Preliminaries
This section defines the problems used in the reductions, grouped by running-time class, and recalls a self-reducibility property of 3SUM.
2 Preliminaries
- The section organizes reduction problems by their time complexity and closes with a 3SUM self-reducibility property.Source: §2 · p. 6
2.1 Problems in eO
- AE-Mono∆ asks whether each edge in an n-node edge-colored graph belongs to a triangle whose edges all share its color.Source: §2.1 · p. 6
2.2 Problems in O
- AE-Sparse∆ asks whether each edge of an m-edge graph belongs to a triangle.Source: §2.2 · p. 7
2.3 Problems in O(n2) time
- 3SUM asks whether three lists contain values a, b, c with a + b = c; common input and equation variants are equivalent by simple reductions.Source: §2.3 · p. 7
2.4 Problems in eO(n1.5) time
- MonoConvolution outputs, for each index i, whether some j satisfies aj = bi−j = ci.Source: §2.4 · p. 7
2.5 Problems in eO
- CoinChange asks for the minimum number of available, repeatable coin values summing to each target; a described algorithm separates heavy and light coins.It computes minimum heavy-coin counts and then runs dynamic programming for light coins.Source: §2.5 · p. 7
2.6 Self-reducibility of 3SUM
- A 3SUM instance reduces to smaller 3SUM instances in linear time in their total size, preserving yes-instances by an OR across the outputs.Source: §2.6 · p. 7
3 Reductions for Graph and Matrix Problems
The section develops reductions linking AE-MonoΔ to intermediate matrix and graph problems. It also relates AE-MonoΔ to sparse triangle detection and 3SUM.
AE-MonoΔ and AE-SparseΔ
- AE-SparseΔ algorithms yield polynomial improvements for AE-MonoΔ, by handling dense color classes separately with fast matrix multiplication.The method applies sparse-triangle algorithms to remaining color subgraphs and uses fast matrix multiplication on the largest subgraphs.Source: §3 · p. 8
Reductions to AE-MonoΔ
- AE-MonoΔ solves MinWitness with O(log n) calls through parallel binary search that halves all output-entry intervals in each call.The reduction labels a tripartite graph so monochromatic triangles identify which half-interval contains each entry.Source: §3 · pp. 8–9
- UnweightedAPSP reduces to AE-MonoΔ with O(log^2 n) calls, using repeated distance-range refinement across logarithmic rounds.Each round computes distances up to a doubled threshold, and AE-MonoΔ calls refine the candidate intervals.Source: §3 · pp. 9–10
3SUM hardness
- AE-MonoΔ is 3SUM-hard via a reduction that combines sparse-triangle instances into monochromatic-triangle instances.Randomly permuted instances are combined by separating repeated edges into numbered groups and considering triples of edge numbers.Source: §3 · p. 10
Reductions to Min-Max
- MinWitness and UnweightedAPSP also reduce to Min-Max, with the latter using two Min-Max calls per distance-doubling round.The MinWitness reduction encodes its output as a Min-Max product; the APSP reduction exploits the structure of unweighted shortest-path matrices.Source: §3 · p. 11
4 Reductions for Convolution Problems
The section gives reductions in both directions between MonoConvolution and 3SUM, establishing a fine-grained equivalence between problems with different known running times. It also reduces CoinChange to MonoConvolution.
MonoConvolution and 3SUM
- The section provides two reductions showing that MonoConvolution is fine-grained equivalent to 3SUM. Best known MonoConvolution algorithms require n^(3/2)-o(1) time, while best 3SUM algorithms require n^2-o(1) time.Source: §4 · p. 11
3SUM to MonoConvolution
- The reduction from 3SUM to MonoConvolution uses hashing, independent copies to control false positives, and shifted instances to combine convolution inputs.The construction embeds multiple All-Integers 3SUM instances into a polylogarithmic number of MonoConvolution instances.Source: §4 · pp. 12–13
MonoConvolution to 3SUM
- For the reverse reduction, frequent values are handled with FFT, while low-frequency values are solved through All-Integers 3SUM.A frequency threshold separates the cases; the threshold is optimized to obtain the stated runtime.Source: §4 · pp. 13–14
CoinChange
- CoinChange reduces to MonoConvolution through O(log n) calls that refine coin-count intervals across successive rounds.Each round computes a doubled count threshold, and a MonoConvolution call distinguishes the even and odd candidate counts.Source: §4 · pp. 14–15