Computing Generalized Convolutions Faster Than Brute Force

In this paper, we consider a general notion of convolution. Let $$ be a finite domain and let $$ be the set of n-length vectors (tuples) of $$. Let $$ be a function and let $$ be a coordinate-wise application of f. The $$-Convolution of two functions $$ is for every $$. This problem generalizes many fundamental convolutions such as Subset Convolution, XOR Product, Covering Product or Packing Product, etc. For arbitrary function f and domain $$ we can compute $$-Convolution via brute-force enumeration in $$ time. Our main result is an improvement over this naive algorithm. We show that $$-Convolution can be computed exactly in $$ for constant $$ when $$ has even cardinality. Our main observation is that a cyclic partition of a function $$ can be used to speed up the computation of $$-Convolution, and we show that an appropriate cyclic partition exists for every f. Furthermore, we demonstrate that a single entry of the $$-Convolution can be computed more efficiently. In this variant, we are given two functions $$ alongside with a vector $$ and the task of the $$-Query problem is to compute integer $$. This is a generalization of the well-known Orthogonal Vectors problem. We show that $$-Query can be computed in $$ time, where $$ is the exponent of currently fastest matrix multiplication algorithm.