License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2022.12
URN: urn:nbn:de:0030-drops-173685
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17368/
Esmer, Barış Can ;
Kulik, Ariel ;
Marx, Dániel ;
Schepper, Philipp ;
Węgrzycki, Karol
Computing Generalized Convolutions Faster Than Brute Force
Abstract
In this paper, we consider a general notion of convolution. Let D be a finite domain and let Dⁿ be the set of n-length vectors (tuples) of D. Let f : D × D → D be a function and let ⊕_f be a coordinate-wise application of f. The f-Convolution of two functions g,h : Dⁿ → {-M,…,M} is (g ⊛_f h)(v) := ∑_{v_g,v_h ∈ D^n s.t. v = v_g ⊕_f v_h} g(v_g) ⋅ h(v_h) for every ? ∈ Dⁿ. 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 ?̃(|D|^{2n} ⋅ polylog(M)) time.
Our main result is an improvement over this naive algorithm. We show that f-Convolution can be computed exactly in ?̃((c ⋅ |D|²)ⁿ ⋅ polylog(M)) for constant c := 5/6 when D has even cardinality. Our main observation is that a cyclic partition of a function f : D × D → 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ⁿ → {-M,…,M} alongside with a vector ? ∈ Dⁿ and the task of the f-Query problem is to compute integer (g ⊛_f h)(?). This is a generalization of the well-known Orthogonal Vectors problem. We show that f-Query can be computed in ?̃(|D|^{(ω/2)n} ⋅ polylog(M)) time, where ω ∈ [2,2.373) is the exponent of currently fastest matrix multiplication algorithm.
BibTeX - Entry
@InProceedings{esmer_et_al:LIPIcs.IPEC.2022.12,
author = {Esmer, Bar{\i}\c{s} Can and Kulik, Ariel and Marx, D\'{a}niel and Schepper, Philipp and W\k{e}grzycki, Karol},
title = {{Computing Generalized Convolutions Faster Than Brute Force}},
booktitle = {17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
pages = {12:1--12:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-260-0},
ISSN = {1868-8969},
year = {2022},
volume = {249},
editor = {Dell, Holger and Nederlof, Jesper},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17368},
URN = {urn:nbn:de:0030-drops-173685},
doi = {10.4230/LIPIcs.IPEC.2022.12},
annote = {Keywords: Generalized Convolution, Fast Fourier Transform, Fast Subset Convolution}
}
|
Keywords: |
|
Generalized Convolution, Fast Fourier Transform, Fast Subset Convolution |
|
Collection: |
|
17th International Symposium on Parameterized and Exact Computation (IPEC 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
14.12.2022 |
