Computing the convolution $A\star B$ of two length-$n$ vectors $A,B$ is an ubiquitous computational primitive. Applications range from string problems to Knapsack-type problems, and from 3SUM to All-Pairs Shortest Paths. These applications often come in the form of nonnegative convolution, where the entries of $A,B$ are nonnegative integers. The classical algorithm to compute $A\star B$ uses the Fast Fourier Transform and runs in time $O(n\log n)$. However, often $A$ and $B$ satisfy sparsity conditions, and hence one could hope for significant improvements. The ideal goal is an $O(k\log k)$-time algorithm, where $k$ is the number of non-zero elements in the output, i.e., the size of the support of $A\star B$. This problem is referred to as sparse nonnegative convolution, and has received considerable attention in the literature; the fastest algorithms to date run in time $O(k\log^2 n)$. The main result of this paper is the first $O(k\log k)$-time algorithm for sparse nonnegative convolution. Our algorithm is randomized and assumes that the length $n$ and the largest entry of $A$ and $B$ are subexponential in $k$. Surprisingly, we can phrase our algorithm as a reduction from the sparse case to the dense case of nonnegative convolution, showing that, under some mild assumptions, sparse nonnegative convolution is equivalent to dense nonnegative convolution for constant-error randomized algorithms. Specifically, if $D(n)$ is the time to convolve two nonnegative length-$n$ vectors with success probability $2/3$, and $S(k)$ is the time to convolve two nonnegative vectors with output size $k$ with success probability $2/3$, then $S(k)=O(D(k)+k(\log\log k)^2)$. Our approach uses a variety of new techniques in combination with some old machinery from linear sketching and structured linear algebra, as well as new insights on linear hashing, the most classical hash function.
翻译:计算 convolution $A\ star B$, 以两个长度- 美元矢量计算 $A, 美元B$是一个无处不在的计算原始。 应用范围从字符串问题到Knapsack 类型问题, 从 3SUM 到 All- Pairs 最短路径。 这些应用程序通常以非负式的组合形式出现, $A, B$的条目是非负式的整数。 以 A\ star B 美元计算 $的经典算法使用快速 Freyier 变换, 并运行时间 $O( nlog n) 。 然而, 通常以美元和 $B$ 满足了快速的算法条件, 因此人们可以期望显著的改进。 理想的目标是 $(k\ logk) 美元- 时间算法, 美元为, 美元, 美元为 美元 美元 算算算为 。 美元 美元 。 美元 以 美元 数字 的算算算算 。