AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

In 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 \rightarrow 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 \rightarrow \{-M,\dots,M\}$ is \[ (g \circledast_f h)(v) = \sum_{v_g,v_h \in D^n \text{s.t. } v = v_g \oplus_f v_h} g(v_g) \cdot h(v_h) \] 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 roughly $O(|D|^{2n}}$ time.

Our main result is an improvement over this naive algorithm. We show that $f$-Convolution can be computed exactly in roughly $O((c \cdot |D|^2)^n)$ time for constant $c = 5/6$ when $D$ has even cardinality.

Roohani Sharma

+49 681 9325 1116

--email hidden

Zoom

527 278 8807

passcode not visible

logged in users only

The talk will take place in the hybrid format. If you wish to attend the talk virtually but do not have the password, contact Roohani Sharma at rsharma@mpi-inf.mpg.de.