Computing Generalized Convolutions Faster Than Brute Force

Zusammenfassung

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,\ldots,M\}$ is \begin{displaymath} (g \circledast_f h)(v) := \sum_{\substack{v_g,v_h \in D^n\\ \text{s.t. } v = v_g \oplus_f v_h}} g(v_g) \cdot h(v_h) \end{displaymath} for every $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}}$ 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}}$ for constant $c := 5/6$ 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,\ldots,M\}$ alongside with a vector $v \in D^n$ and the task of the $f$-Query problem is to compute integer $(g \circledast_f h)(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}}$ time, where $\omega \in [2,2.373)$ is the exponent of currently fastest matrix multiplication algorithm.