Send email Copy Email Address
2022-10-13

Computing Generalized Convolutions Faster Than Brute Force

Summary

In this paper, we consider a general notion of convolution. Let $\Dd$ be a finite domain and let $\Dd^n$ be the set of $n$-length vectors (tuples) of $\Dd$. Let $f \from \Dd \times \Dd \to \Dd$ be a function and let $\oplus_f$ be a coordinate-wise application of $f$. The \fConv of two functions $g,h \from \Dd^n \to \{-M,\ldots,M\}$ is \begin{displaymath} (g \fconv h)(\bv) \deff \sum_{\substack{\bv_g,\bv_h \in \Dd^n\\ \text{s.t. } \bv = \bv_g \oplus_f \bv_h}} g(\bv_g) \cdot h(\bv_h) \end{displaymath} for every $\bv \in \Dd^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 $\Dd$ we can compute \fConv via brute-force enumeration in $\Oc{|\Dd|^{2n}}$ time. Our main result is an improvement over this naive algorithm. We show that \fConv can be computed exactly in $\Oc{ (c \cdot |\Dd|^2)^{n}}$ for constant $c \deff 5/6$ when $\Dd$ has even cardinality. Our main observation is that a \emph{cyclic partition} of a function $f \from \Dd \times \Dd \to \Dd$ can be used to speed up the computation of \fConv, and we show that an appropriate cyclic partition exists for every $f$. Furthermore, we demonstrate that a single entry of the \fConv can be computed more efficiently. In this variant, we are given two functions $g,h \from \Dd^n \to \{-M,\ldots,M\}$ alongside with a vector $\bv \in \Dd^n$ and the task of the \fquery problem is to compute integer $(g \fconv h)(\bv)$. This is a generalization of the well-known Orthogonal Vectors problem. We show that \fquery can be computed in $\Oc{|\Dd|^{\frac{\omega}{2} n}}$ time, where $\omega \in [2,2.373)$ is the exponent of currently fastest matrix multiplication algorithm.

Conference / Medium

17th International Symposium on Parameterized and Exact Computation (IPEC 2022)

Date published

2022-10-13

Date last modified

2022-10-14 12:34:15