Computing generalized convolutions faster than brute force

(g otimes_f h)( extbf{v}) := sum_{substack{ extbf{v}_g, extbf{v}_h in D^n\ ext{s.t. } extbf{v}_g oplus_f extbf{v}_h}} g( extbf{v}_g) cdot h( extbf{v}_h)

for every

e x t b f v i n 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

w i d e t i l d e O (| D |^{2 n} m a t h r m p o l y l o g (M))

time. Our main result is an improvement over this naive algorithm. We show that

f

-Convolution can be computed exactly in

w i d e t i l d e O ((c c d o t | D |^{2})^{n} m a t h r m p o l y l o g (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 i m e s D o 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} o - M, l d o t s, M

alongside with a vector

e x t b f v i n D^{n}

and the task of the

f

-Query problem is to compute integer

(g o t i m e s_{f} h) (e x t b f v)

. This is a generalization of the well-known Orthogonal Vectors problem. We show that

f

-Query can be computed in

w i d e t i l d e O (| D |^{f r a c o m e g a 2 n} m a t h r m p o l y l o g (M))

time, where

o m e g a i n [2, 2.372)

is the exponent of currently fastest matrix multiplication algorithm.

Cites work

This page was built for publication: Computing generalized convolutions faster than brute force

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6185947)