Computing Generalized Convolutions Faster Than Brute Force

Abstract

In this paper, we consider a general notion of convolution. Let $D$ be a finite domain and let $D^n$ be the set of $n$-length vectors (tuples) of $D$. Let $f:D\times D\to D$ be a function and let ${\oplus }_f$ be a coordinate-wise application of $f$. The $f$-Convolution of two functions $g,h:D^n\to \{-M,\dots ,M\}$ is $$(g{\otimes }_{f}h)(\text{v}):=\sum _{\begin{array}{c}{\text{v}}_g,{\text{v}}_h\in D^n\\ \text{s.t. }{\text{v}}_g{\oplus }_f{\text{v}}_h\end{array}}g({\text{v}}_g)\cdot h({\text{v}}_h)$$ for every $\text{v}\in D^n$. This problem generalizes many fundamental convolutions such as Subset Convolution, XOR Product, Covering Product or Packing Product, etc. For arbitrary function $f$ and domain $D$ we can compute $f$-Convolution via brute-force enumeration in $\tilde{O}(|D{|}^{2n}\mathrm{polylog}(M))$ time. Our main result is an improvement over this naive algorithm. We show that $f$-Convolution can be computed exactly in $\tilde{O}((c\cdot |D{|}^2{)}^n\mathrm{polylog}(M))$ for constant $c:=3/4$ when $D$ has even cardinality. Our main observation is that a \emph{cyclic partition} of a function $f:D\times D\to D$ can be used to speed up the computation of $f$-Convolution, and we show that an appropriate cyclic partition exists for every $f$. Furthermore, we demonstrate that a single entry of the $f$-Convolution can be computed more efficiently. In this variant, we are given two functions $g,h:D^n\to \{-M,\dots ,M\}$ alongside with a vector $\text{v}\in D^n$ and the task of the $f$-Query problem is to compute integer $(g{\otimes }_{f}h)(\text{v})$. This is a generalization of the well-known Orthogonal Vectors problem. We show that $f$-Query can be computed in $\tilde{O}(|D{|}^{\frac{\omega }{2}n}\mathrm{polylog}(M))$ time, where $\omega \in [2,2.372)$ is the exponent of currently fastest matrix multiplication algorithm.

We improved constant c, 29 pages, 5 colored figures