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 nlength vectors (tuples) of D. Let f : D × D → D be a function and let ⊕_f be a coordinatewise application of f. The fConvolution 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 fConvolution via bruteforce enumeration in 𝒪̃(D^{2n} ⋅ polylog(M)) time.
Our main result is an improvement over this naive algorithm. We show that fConvolution 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 fConvolution, and we show that an appropriate cyclic partition exists for every f.
Furthermore, we demonstrate that a single entry of the fConvolution 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 fQuery problem is to compute integer (g ⊛_f h)(𝐯). This is a generalization of the wellknown Orthogonal Vectors problem. We show that fQuery 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:112:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772600},
ISSN = {18688969},
year = {2022},
volume = {249},
editor = {Dell, Holger and Nederlof, Jesper},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17368},
URN = {urn:nbn:de:0030drops173685},
doi = {10.4230/LIPIcs.IPEC.2022.12},
annote = {Keywords: Generalized Convolution, Fast Fourier Transform, Fast Subset Convolution}
}
14.12.2022
Keywords: 

Generalized Convolution, Fast Fourier Transform, Fast Subset Convolution 
Seminar: 

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

Issue date: 

2022 
Date of publication: 

14.12.2022 