CISPA
Browse

Computing Generalized Convolutions Faster Than Brute Force

Download (696.52 kB)
journal contribution
posted on 2024-03-26, 08:58 authored by Baris Can EsmerBaris Can Esmer, Ariel Kulik, Dániel MarxDániel Marx, Philipp SchepperPhilipp Schepper, Karol Węgrzycki

 In this paper, we consider a general notion of convolution. Let D be a finite domain and let Dn 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:Dn→{−M,…,M} is

(g⊗fh)(v):=∑vg,vh∈Dns.t. vg⊕fvhg(vg)⋅h(vh)

for every v∈Dn. 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 O˜(|D|2npolylog(M)) time.
Our main result is an improvement over this naive algorithm. We show that f-Convolution can be computed exactly in O˜((c⋅|D|2)npolylog(M)) for constant c:=3/4 when D has even cardinality. Our main observation is that a \emph{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:Dn→{−M,…,M} alongside with a vector v∈Dn and the task of the f-Query problem is to compute integer (g⊗fh)(v). This is a generalization of the well-known Orthogonal Vectors problem. We show that f-Query can be computed in O˜(|D|ω2npolylog(M)) time, where ω∈[2,2.372) is the exponent of currently fastest matrix multiplication algorithm. 

History

Primary Research Area

  • Algorithmic Foundations and Cryptography

Journal

Algorithmica: an international journal in computer science

Volume

86

Page Range

334-366

Publisher

Springer Nature

Open Access Type

  • Hybrid

Sub Type

  • Article

BibTeX

@article{Esmer:Kulik:Marx:Schepper:Węgrzycki:2024, 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", year = 2024, month = 1, journal = "Algorithmica: an international journal in computer science", number = "1", pages = "334--366", publisher = "Springer Nature", issn = "0178-4617", doi = "10.1007/s00453-023-01176-2" }

Usage metrics

    Categories

    No categories selected

    Licence

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC