标题： 更快的卷积：重新审视Yates和Strassen 显示英文标题

标题： Faster Convolutions: Yates and Strassen Revisited

摘要： 给定两个向量$u,v \in \mathbb{Q}^D$在有限域$D$上和一个函数$f : D\times D\to D$，卷积问题要求计算向量$w \in \mathbb{Q}^D$，其条目由$w(d) = \sum_{\substack{x,y \in D \\ f(x,y)=d}} u(x)v(y).$定义。在参数化和指数时间算法中，乘积域上的卷积尤为突出：这里固定一个有限域$B$和一个函数$h : B \times B \to B$，并在乘积域$D = B^k$上使用函数$h^k :D \times D\to D$进行卷积，该函数将$h$分量地应用于其输入元组。 我们通过多线性代数提供了关于产品域卷积的新视角。 这一观点简化了现有算法（如van Rooij等人，ESA 2009）的表述与分析。 此外，利用快速矩阵乘法理论中的已知结果，我们推导出改进的 $O^\ast(|B|^{2\omega/3 \cdot k}) = O(|D|^{1.582})$ 时间复杂度算法，超越了Esmer等人（Algorithmica 86(1), 2024）提出的先前上界 $c^k |B|^{2k}$ 对于 $c < 1$ 的形式。 使用本文描述的设置，代数复杂性理论中的Strassen渐近秩猜想将意味着准线性的 $|D|^{1+o(1)}$ 时间复杂度算法。 这一猜想最近引起了算法社区的关注。 (Björklund-Kaski和Pratt, STOC 2024; Björklund等人, SODA 2025) 我们的论文旨在为算法领域的读者提供一个自包含的阐述，并包含所有必要的数学背景知识，采用明确的基于坐标的表示法。 特别是，我们假定没有抽象代数的知识。 显示英文摘要

摘要： 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.