Pith. sign in

REVIEW 1 major objections 4 minor 17 references

Faster Convolutions: Yates and Strassen Revisited

T0 review · 1 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Product-structured convolutions reduce to fast matrix multiplication, yielding an O(N^1.582) algorithm.

desk verdict Correct core bound, but Lemma 3.1's proof is misaligned as printed and needs a fix before publication. read the letter →

arxiv 2505.22410 v1 pith:GJ5QY5JQ submitted 2025-05-28 cs.DS cs.CC

Cornelius Brand , Radu Curticapean , Baitian Li , Kevin Pratt This is my paper
classification cs.DScs.CC
keywords generalizedconvolutionsproductdomainsfastmatrixmultiplicationtensorrankYates'algorithmasymptoticconjecturetreedecompositionssplit-and-list
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Convolution over a product domain $B^k$, where the combining function applies a fixed partial map $h$ coordinate-wise, sits at the heart of join-node computations in treewidth-based algorithms. This paper's central claim is that such convolutions are far cheaper than the naive quadratic bound: they can be embedded into multiplication of square matrices of size $|B|^{2\lceil k/3\rceil}$, and with the current matrix multiplication exponent $\omega<2.372$ this gives $O(|B|^{2\omega/3\cdot k}) = O(|B|^{1.582k})$ operations. That improves the best previous general upper bound of the form $c^k |B|^{2k}$ with $c<1$. The paper also shows that when the base function has a rank-$r$ decomposition, Yates' algorithm evaluates the lifted decomposition in $O(r^k k)$ time, which lets known $O^*(3^t)$ and $O^*(2^t)$ algorithms for dominating sets and perfect matchings be recovered mechanically instead of by problem-specific cleverness. If Strassen's asymptotic rank conjecture holds, the same framework would yield quasi-linear $|B|^{k+o(k)}$ time for all product-type convolutions.

What carries the argument

Two mechanisms carry the argument. The first is the bilinear split-and-list embedding of Lemma 3.1: from $u,v\in\mathbb{Q}^{D^3}$ one forms $U_{a,b;i,j}=\sum_{\ell:f(\ell,j)=b}u_{a,i,\ell}$ and $V_{i,j;c,d}=\sum_{k:f(i,k)=d}v_{c,k,j}$, and then the linear projection $\phi(e_{a,b;c,d})=e_{f(a,c),b,d}$ satisfies $u\circledast_{f^3}v=\phi(U\cdot V)$. This reduces the third power of any convolution to multiplying two $D^2\times D^2$ matrices, and applying it blockwise over the $k$ coordinates of $B^k$ is what yields the $|B|^{2\omega/3\cdot k}$ bound. The second is Yates' algorithm: given a rank-$r$ decomposition of the base function $h$, the Kronecker product decomposition (Lemma 2.3) lifts it to rank at most $r^k$ for $h^k$, and the lifted inner products can be evaluated by an $r$-ary tree in $O(r^k k)$ arithmetic operations.

What would settle it

Compute the two sides of Lemma 3.1 for a small base domain, for example $B=\{0,1\}$ with $h$ the OR function and $k=3$: build $u,v\in\mathbb{Q}^{B^3}$ with random entries, compute $\phi(U\cdot V)$ exactly as the proof defines $U$ and $V$, and compare it entrywise with the naive $f^3$-convolution after reordering the output coordinates according to the definition of $\circledast_{f^3}$. A mismatch on any entry shows the proof requires an explicit coordinate permutation; equality on all $|B|^3$ entries confirms the reduction.

Watch

Extended reading notes

Core claim

The discovery is a uniform bilinear 'split-and-list' embedding. For any partial function $f:D\times D\to D$, the convolution associated with the third power $f^3$ can be rewritten as $\phi(U\cdot V)$, where $U$ and $V$ are $D^2\times D^2$ matrices whose entries are linear combinations of the input vectors, and $\phi$ is a linear projection. Applying this embedding blockwise to the $k$ coordinates of a product-structured convolution over $B^k$ turns the whole computation into a single matrix product of size $|B|^{2\lceil k/3\rceil}$, so fast matrix multiplication yields $O(|B|^{2\omega/3\cdot k})$ operations. The same language gives a clean proof of Yates' algorithm: a rank-$r$ decomposition of the base function lifts via Kronecker products to a rank at most $r^k$ decomposition of $h^k$, and the lifted inner products can be collected in $O(r^k k)$ time. Together these results establish that product-structured convolutions, for arbitrary partial base functions, run in $O(N^{2\omega/3})=O(N^{1.582})$ time on a domain of size $N=|B|^k$.

Load-bearing premise

The running-time bound rests on the unstated coordinate permutation inside Lemma 3.1: the indices of $u$ and $v$ must be relabeled as $(a,i,\ell)\mapsto(a,\ell,i)$ and $(c,k,j)\mapsto(c,j,k)$ for the projected matrix product to equal the $f^3$-convolution, and if that alignment is wrong the claimed reduction collapses.

Editorial extensions

If this is right

  • Every convolution on a product domain $B^k$ with a fixed base function $h$—covering product, XOR convolution, subset convolution, and the dominating-set join—inherits the $O(|B|^{2\omega/3\cdot k})$ bound, independent of the semantic meaning of the states.
  • The reduction of Lemma 3.1 works for every partial function $f$, not only product-structured ones, so any future fast matrix multiplication algorithm automatically improves all such convolutions by the same exponent factor.
  • Yates' algorithm turns a rank bound for the base function into a concrete running time $O(r^k k)$; consequently, finding rank-$r$ decompositions for the base functions of classical problems reproduces the known $O(3^t)$ dominating-set and $O(2^t)$ perfect-matching algorithms in a mechanical way.
  • Under Strassen's asymptotic rank conjecture, Theorem 2.7 gives $O(|D|^{k+o(k)})$ time, meaning all product-type convolutions become quasi-linear in the size of the product domain $|D|^k$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The unstated coordinate permutation in Lemma 3.1 appears repairable by choosing a consistent flattening convention for $D^3$, but making it explicit would be necessary before the reduction can be implemented exactly as written.
  • A natural next test is whether the $|B|^{2\omega/3\cdot k}$ bound is tight for product-structured convolutions or whether rank lower bounds force a larger exponent; the paper does not address lower bounds.
  • Because the split-and-list embedding recasts join-node computation as matrix multiplication, optimized matrix libraries could bring the asymptotic speed-up into practice for the small domains used in treewidth algorithms; this is an empirical extension the paper does not test.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 4 minor

Summary. The paper studies the computation of convolutions over product domains D = B^k defined by a coordinate-wise function h^k. It reformulates such convolutions as bilinear maps and rank decompositions, proves a Yates-style algorithm (Theorem 2.5), and then proves a Strassen-style embedding theorem (Theorem 2.6) showing that any product-structured convolution can be reduced to fast matrix multiplication, yielding O^*(|B|^{2ω/3·k}) ≈ O(|D|^{1.582k}) time. It further observes that the asymptotic rank conjecture would give quasi-linear O(|D|^{k+o(k)}) time for all product-type convolutions. The paper is explicitly expository, aiming to give a self-contained account for an algorithms audience and to show that low-rank tensor decompositions can replace some of the ad-hoc state-encoding tricks in treewidth DP algorithms.

Significance. If the proofs are correct, the paper provides a clean unifying framework for join-node convolutions in treewidth DP and improves on the best known general bounds for product-domain convolutions, matching the state of the art from algebraic complexity theory. The conditional quasi-linear time consequence is valuable and connects to active research on the asymptotic rank conjecture. The paper's strengths are its didactic framing, explicit coordinate notation, and the clear separation between the unconditional matrix-multiplication result and the conditional asymptotic-rank result. However, the main algorithmic theorem is not new—it is Strassen's embedding—and the paper's contribution is primarily expository; the central proof has a coordinate-alignment error that must be repaired.

major comments (1)
  1. [Section 3, Lemma 3.1] As printed, the construction does not compute the f^3-convolution. With U_{a,b;i,j} = Σ_{ℓ:f(ℓ,j)=b} u_{a,i,ℓ} and V_{i,j;c,d} = Σ_{k:f(i,k)=d} v_{c,k,j}, the expansion gives φ(U·V) = Σ_{a,c,i,j,k,ℓ} u_{a,i,ℓ} v_{c,k,j} e_{f(a,c), f(ℓ,j), f(i,k)}. Matching this to the f^3-convolution output (f(i1,j1), f(i2,j2), f(i3,j3)) requires (i1,i2,i3) = (a,ℓ,i) and (j1,j2,j3) = (c,j,k), which yields coefficient u_{i1,i3,i2} v_{j1,j3,j2} rather than the required u_{i1,i2,i3} v_{j1,j2,j3}. The map φ therefore computes a coordinate-permuted version of the desired convolution. This is repairable: define U by summing u_{a,ℓ,i} and V by summing v_{c,j,k}. Because Theorem 2.6 is proved by applying Lemma 3.1, this correction is load-bearing and must be made explicit.
minor comments (4)
  1. [Section 3, proof of Theorem 2.6] The reduction overhead is stated as O(|D|^{2n}), but Lemma 3.1 gives O(|D|^{4n}) for building U, V, and φ. The final bound is unaffected because the matrix multiplication term O(|D|^{2ω n}) dominates for ω > 2, but the displayed equality should be corrected to O(|D|^{2ω n} + |D|^{4n}) = O(|D|^{2ω n}).
  2. [Abstract and Theorem 2.6] The abstract writes O(|D|^{1.582}) while the theorem statement gives O(|D|^{1.582k}); the exponent k should appear in the abstract as well.
  3. [Section 4, proof of Theorem 2.5] The vector f_ι is described as having dimension k−i; from the recursion it must have dimension |B|^{k−i}. Also, the sentence 'At layer k, we interpret (x_k ... x_{k−1}) as empty' contains an obvious off-by-one typo.
  4. [Theorems 2.5 and 2.6] The notation D is overloaded: earlier D = B^k is the product domain, while in Theorem 2.6 D denotes the base domain and the product is D^k. This ambiguity should be resolved, for instance by renaming the base domain to B throughout.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: Theorem 2.6 is proven from Strassen's external embedding (Lemma 3.1) and the matrix-multiplication exponent; nothing is fitted, predicted from its own fit, or forced by author-only citations.

full rationale

The main algorithmic claim (Theorem 2.6) is derived in Section 3 by reducing the f^3-convolution to a D^2 by D^2 matrix product plus a linear projection (Lemma 3.1). This reduction is a direct algebraic identity using Strassen's external 1988 construction; it does not assume the claimed running time, and it does not invoke any of the authors' prior results. Yates's algorithm (Theorem 2.5) is proved from scratch in Section 4. Theorem 2.7 is explicitly conditional on Strassen's asymptotic rank conjecture [13] and is therefore not presented as an unconditional derivation. The papers with overlapping authorship ([2], [10]) are cited only for background on the asymptotic rank conjecture and fine-grained connections; they are not needed for Theorem 2.6's proof. The only notable issue in the printed proof is a local coordinate-ordering typo in Lemma 3.1: as displayed, U and V are built from u_{a,i,ell} and v_{c,k,j} while phi produces e_{f(a,c),f(ell,j),f(i,k)}; relabeling u as (a,ell,i) and v as (c,j,k) makes the identity exact. This is a repairable proof-presentation error, not a case where a prediction reduces to its input by construction. Accordingly, no circular step is present.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The main theorem depends only on standard facts (fast matrix multiplication, tensor rank lifting) plus the unstated coordinate alignment in Lemma 3.1; the asymptotic rank conjecture appears only as a conditional. No new entities or fitted parameters are introduced.

assumptions (3)
  • standard math Fast matrix multiplication with exponent ω < 3 is available over Q.
    Theorem 2.6 and Section 3 use ω as a black box; this is a standard background result in algebraic complexity.
  • ad hoc to paper Strassen's asymptotic rank conjecture: product-structured tensors over B^k have rank |B|^{k+o(k)}.
    Theorem 2.7 is conditional on this open conjecture; it is not used for the main bound.
  • ad hoc to paper The coordinate permutation implicit in Lemma 3.1 aligns the matrix-product projection with the f^3-convolution output ordering.
    The proof of Lemma 3.1 relies on a silent relabeling of input coordinates (a,i,ℓ) to (a,ℓ,i) and (c,k,j) to (c,j,k); without this alignment the matrix product does not compute the convolution.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Faster Convolutions: Yates and Strassen Revisited." pith.science (2026). https://pith.science/paper/GJ5QY5JQ

@misc{pith2026250522410,
  author       = {Pith},
  title        = {Pith review of: Faster Convolutions: Yates and Strassen Revisited},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GJ5QY5JQ}},
  note         = {Machine review of arXiv:2505.22410}
}
abstract

Given two vectors $u,v \in \mathbb{Q}^D$ over a finite domain $D$ and a function $f : D\times D\to D$, the convolution problem asks to compute the vector $w \in \mathbb{Q}^D$ whose entries are defined by $w(d) = \sum_{\substack{x,y \in D \\ f(x,y)=d}} u(x)v(y).$ In parameterized and exponential-time algorithms, convolutions on product domains are particularly prominent: Here, a finite domain $B$ and a function $h : B \times B \to B$ are fixed, and convolution is done over the product domain $D = B^k$, using the function $h^k :D \times D\to D$ that applies $h$ coordinate-wise to its input tuples. We present a new perspective on product-domain convolutions through multilinear algebra. This viewpoint streamlines the presentation and analysis of existing algorithms, such as those by van Rooij et al. (ESA 2009). Moreover, using established results from the theory of fast matrix multiplication, we derive improved $O^\ast(|B|^{2\omega/3 \cdot k}) = O(|D|^{1.582})$ time algorithms, improving upon previous upper bounds by Esmer et al. (Algorithmica 86(1), 2024) of the form $c^k |B|^{2k}$ for $c < 1$. Using the setup described in this note, Strassen's asymptotic rank conjecture from algebraic complexity theory would imply quasi-linear $|D|^{1+o(1)}$ time algorithms. This conjecture has recently gained attention in the algorithms community. (Bj\"orklund-Kaski and Pratt, STOC 2024, Bj\"orklund et al., SODA 2025) Our paper is intended as a self-contained exposition for an algorithms audience, and it includes all essential mathematical prerequisites with explicit coordinate-based notation. In particular, we assume no knowledge in abstract algebra.

Figures

Figures reproduced from arXiv: 2505.22410 by the authors.

Figure 1
Figure 1. Fix the base domain B = {0, 1} and one of the three base functions h : B × B → B shown in the first row, where blue, pink and white squares correspond to the function values 0, 1, and undefined, respectively. The covering product, XOR and subset convolutions are powers f = h k of the respective base function that induce vector-valued functions t : D × D → {0, 1} D for D = Bk . The functions t are depicted as tensors… view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

17 extracted references · 8 canonical work pages

  1. [1]

    Bodlaender, Henning Fernau, Ton Kloks, and Rolf Niedermeier

    Jochen Alber, Hans L. Bodlaender, Henning Fernau, Ton Kloks, and Rolf Niedermeier. Fixed parameter algorithms for Dominating Set and related problems on planar graphs. Algorithmica, 33(4):461–493, 2002.doi:10.1007/S00453-001-0116-5

    doi:10.1007/s00453-001-0116-5 2002

  2. [2]

    Fast deterministic chromatic number under the asymptotic rank conjecture

    Andreas Bj¨ orklund, Radu Curticapean, Thore Husfeldt, Petteri Kaski, and Kevin Pratt. Fast deterministic chromatic number under the asymptotic rank conjecture. In Yossi Azar and Debmalya Panigrahi, editors,Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025, pages 2804–2818. SIAM,...

    work page doi:10.1137/1.9781611978322.91 2025

  3. [3]

    Fourier meets M¨ obius: Fast subset convolution

    Andreas Bj¨ orklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Fourier meets M¨ obius: Fast subset convolution. In David S. Johnson and Uriel Feige, editors,Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007, pages 67–74. ACM, 2007.doi:10.1145/1250790.1250801

    arXiv 2007

  4. [5]

    Fomin, Lukasz Kowalik, Daniel Lokshtanov, D´ aniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.Parameterized Algorithms

    Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D´ aniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.Parameterized Algorithms. Springer, 2015. doi:10.1007/978-3-319-21275-3

    doi:10.1007/978-3-319-21275-3 2015

  5. [6]

    Computing generalized convolutions faster than brute force.Algorithmica, 86(1):334–366, 2024.doi:10.1007/S00453-023-01176-2

    Baris Can Esmer, Ariel Kulik, D´ aniel Marx, Philipp Schepper, and Karol Wegrzycki. Computing generalized convolutions faster than brute force.Algorithmica, 86(1):334–366, 2024.doi:10.1007/S00453-023-01176-2

    work page doi:10.1007/s00453-023-01176-2 2024

  6. [7]

    Faster algebraic algorithms for path and packing problems

    Ioannis Koutis. Faster algebraic algorithms for path and packing problems. In Luca Aceto, Ivan Damg ˚ ard, Leslie Ann Goldberg, Magn´ us M. Halld´ orsson, Anna Ing´ olfsd´ ottir, and Igor Walukiewicz, editors,Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I: Tack A: Al...

    doi:10.1007/978-3-540 2008

  7. [8]

    Limits and applications of group algebras for parame- terized problems.ACM Trans

    Ioannis Koutis and Ryan Williams. Limits and applications of group algebras for parame- terized problems.ACM Trans. Algorithms, 12(3):31:1–31:18, 2016. doi:10.1145/2885499

    work page doi:10.1145/2885499 2016

  8. [9]

    Known algorithms on graphs of bounded treewidth are probably optimal.ACM Trans

    Daniel Lokshtanov, D´ aniel Marx, and Saket Saurabh. Known algorithms on graphs of bounded treewidth are probably optimal.ACM Trans. Algorithms, 14(2):13:1–13:30, 2018. doi:10.1145/3170442

    doi:10.1145/3170442 2018

Show all 17 references
  1. [10]

    A stronger connection between the asymptotic rank conjecture and the set cover conjecture

    Kevin Pratt. A stronger connection between the asymptotic rank conjecture and the set cover conjecture. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors,Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, ...

    2024

  2. [11]

    The Burnside algebra of a finite group.Journal of Combinatorial Theory, 2(4):603–615, 1967.doi:10.1016/S0021-9800(67)80064-4

    Louis Solomon. The Burnside algebra of a finite group.Journal of Combinatorial Theory, 2(4):603–615, 1967.doi:10.1016/S0021-9800(67)80064-4

    1967 doi

  3. [12]

    Strassen

    V. Strassen. The asymptotic spectrum of tensors.Journal f¨ ur die reine und angewandte Mathematik, 384:102–152, 1988. URL:http://eudml.org/doc/153001

    1988

  4. [13]

    Strassen.Algebra and Complexity, pages 429–446

    V. Strassen.Algebra and Complexity, pages 429–446. Birkh¨ auser Basel, Basel, 1994. doi:10.1007/978-3-0348-9112-7_18

    1994 doi

  5. [14]

    Algorithms for vertex partitioning prob- lems on partialk-trees.SIAM J

    Jan Arne Telle and Andrzej Proskurowski. Algorithms for vertex partitioning prob- lems on partialk-trees.SIAM J. Discret. Math., 10(4):529–550, 1997. doi:10.1137/ S0895480194275825

    1997

  6. [15]

    Fast generalized DFTs for all finite groups

    Chris Umans. Fast generalized DFTs for all finite groups. pages 793–805, 2019. doi: 10.1109/FOCS.2019.00052

    2019

  7. [16]

    Johan M. M. van Rooij, Hans L. Bodlaender, and Peter Rossmanith. Dynamic programming on tree decompositions using generalised fast subset convolution. In Amos Fiat and Peter Sanders, editors,Algorithms - ESA 2009, 17th Annual European Symposium, Copenhagen, Denmark, September ...

    2009 doi

  8. [17]

    Finding paths of length k in O∗(2k) time.Inf

    Ryan Williams. Finding paths of length k in O∗(2k) time.Inf. Process. Lett., 109(6):315–318, 2009.doi:10.1016/J.IPL.2008.11.004

    2009 doi

  9. [18]

    The design and analysis of factorial experiments

    Frank Yates. The design and analysis of factorial experiments. 1937. 13

    1937

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.