Faster Convolutions: Yates and Strassen Revisited

Given two vectors \(u, v \in \mathbb{Q}^D\) over a finite domain \(D\) and a function \(f: D \times D \rightarrow D\), the convolution problem asks to compute the vector \(w \in \mathbb Q^D\) whose entries are defined by \begin{equation}w(d) = \sum_{\substack{x,y \in D \\ f(x,y)=d}} u(x)\, v(y).\end{equation} 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 \rightarrow B\) are fixed, and convolution is done over the product domain \(D = B^k\), using the function \(f = h^k: D \times D \rightarrow D\) that applies \(h\) coordinate-wise to its input tuples.