(2022) Computing Generalized Convolutions Faster Than Brute Force.

Text
ipec.pdf  Submitted Version Download (1MB)  Preview 
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 coordinatewise 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 bruteforce 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 wellknown 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.
Item Type:  Conference or Workshop Item (A Paper) (Paper) 

Divisions:  Dániel Marx (DM) 
Conference:  IPEC International Symposium on Parameterized and Exact Computation (was IWPEC pre 2004) 
Depositing User:  Philipp Schepper 
Date Deposited:  13 Oct 2022 09:15 
Last Modified:  13 Oct 2022 09:15 
Primary Research Area:  NRA1: Trustworthy Information Processing 
URI:  https://publications.cispa.saarland/id/eprint/3835 
Actions
Actions (login required)
View Item 