Browse
- No file added yet -

# Computing Generalized Convolutions Faster Than Brute Force

conference contribution
posted on 2023-11-29, 18:23 authored by, Ariel Kulik, Karol W?grzycki
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.

## Preferred Citation

Baris Esmer, Ariel Kulik, Dániel Marx, Philipp Schepper and Karol W?grzycki. Computing Generalized Convolutions Faster Than Brute Force. In: International Symposium on Parameterized and Exact Computation (IPEC). 2022.

## Primary Research Area

• Algorithmic Foundations and Cryptography

## Name of Conference

International Symposium on Parameterized and Exact Computation (IPEC)

2022-10-13

• Gold

## BibTeX

@inproceedings{cispa_all_3835, title = "Computing Generalized Convolutions Faster Than Brute Force", author = "Esmer, Baris Can and Kulik, Ariel and Marx, Dániel and Schepper, Philipp and W?grzycki, Karol", booktitle="{International Symposium on Parameterized and Exact Computation (IPEC)}", year="2022", }

## Categories

No categories selected

## Exports

RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC
figshare. credit for all your research.