Item

Abstract

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.