论文标题
比蛮力更快地计算广义卷积
Computing Generalized Convolutions Faster Than Brute Force
论文作者
论文摘要
在本文中，我们考虑了卷积的一般概念。令$ d $为有限域，让$ d^n $为$ n $长度向量（元组）$ d $。令$ f：d \ times d \ d $为一个函数，让$ \ oplus_f $为$ f $的坐标应用程序。两个函数的$ f $ -convolution $ g，h：d^n \ to \ { - m，\ ldots，m \} $ is $$（g \ otimes_f h）（\ textbf {v}）：= \ sum _ { d^n \\ \ text {s.t。 } \ textbf {v} _g \ oplus_f \ textbf {v} _h}} g（\ textbf {v} _g）\ cdot h（\ cdot h（\ textbf {v} _h）$这个问题概括了许多基本卷积，例如子集卷积，XOR产品，覆盖产品或包装产品等。对于任意功能$ f $和域$ d $，我们可以通过Brute-Force枚举$ \ widetilde {o}（O}（O}（O}）（| dn} \ d |^{2n} \ Mathrm {polylylog $）（polylylip）（M） 我们的主要结果是对这种天真算法的改进。我们表明，$ f $ -convolution可以在$ \ widetilde {o}（（（c \ cdot | d |^2）^{n} \ mathrm {polylog}（m））$中，对于常数$ c：= 3/4 $时，$ d $当$ d $具有Cardinatity时。我们的主要观察结果是，函数$ f：d \ times d \ d $ d $的\ emph {环状分区}可以用来加快$ f $ -convolution的计算，我们证明每个$ f $都存在适当的环形分区。 此外，我们证明可以更有效地计算出$ f $ convolution的单个条目。在此变体中，我们得到了两个函数$ g，h：h：d^n \ to \ { - m，\ ldots，m \} $以及vector $ \ textbf {v} \ in d^n $中的任务，$ f $ - 问题问题的任务是计算integer $（g \ otimes___f h）$ n $ fextbf。这是众所周知的正交矢量问题的概括。我们表明，$ f $ -query可以在$ \ widetilde {o}（| d |^{\fracΩ{\fracΩ{2} n} \ mathrm {polylog}（m））$ time中计算，其中$ω\ in [2,2.372）$是当前快速的矩阵乘数的代价。
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 \to 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 \to \{-M,\ldots,M\}$ is $$(g \otimes_f h)(\textbf{v}) := \sum_{\substack{\textbf{v}_g,\textbf{v}_h \in D^n\\ \text{s.t. } \textbf{v}_g \oplus_f \textbf{v}_h}} g(\textbf{v}_g) \cdot h(\textbf{v}_h)$$ for every $\textbf{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 $\widetilde{O}(|D|^{2n}\mathrm{polylog}(M))$ time. Our main result is an improvement over this naive algorithm. We show that $f$-Convolution can be computed exactly in $\widetilde{O}((c \cdot |D|^2)^{n}\mathrm{polylog}(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 \times D \to 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 \to \{-M,\ldots,M\}$ alongside with a vector $\textbf{v} \in D^n$ and the task of the $f$-Query problem is to compute integer $(g \otimes_f h)(\textbf{v})$. This is a generalization of the well-known Orthogonal Vectors problem. We show that $f$-Query can be computed in $\widetilde{O}(|D|^{\fracω{2} n}\mathrm{polylog}(M))$ time, where $ω\in [2,2.372)$ is the exponent of currently fastest matrix multiplication algorithm.
