cispa_all_3835.pdf (1021.51 kB)

# Computing Generalized Convolutions Faster Than Brute Force

conference contribution

posted on 2023-11-29, 18:23 authored by Baris Can EsmerBaris Can Esmer, Ariel Kulik, Dániel MarxDániel Marx, Philipp SchepperPhilipp Schepper, Karol W?grzyckiIn 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.

## History

## 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)## Legacy Posted Date

2022-10-13## Open Access Type

- 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", }## Usage metrics

## Categories

No categories selected## Licence

## Exports

RefWorks

BibTeX

Ref. manager

Endnote

DataCite

NLM

DC