hide
Free keywords:
Computer Science, Data Structures and Algorithms, cs.DS
Abstract:
Computing the convolution $A\star B$ of two length-$n$ integer vectors $A,B$
is a core problem in several disciplines. It frequently comes up in algorithms
for Knapsack, $k$-SUM, All-Pairs Shortest Paths, and string pattern matching
problems. For these applications it typically suffices to compute convolutions
of nonnegative vectors. This problem can be classically solved in time $O(n\log
n)$ using the Fast Fourier Transform.
However, often the involved vectors are sparse and hence one could hope for
output-sensitive algorithms to compute nonnegative convolutions. This question
was raised by Muthukrishnan and solved by Cole and Hariharan (STOC '02) by a
randomized algorithm running in near-linear time in the (unknown) output-size
$t$. Chan and Lewenstein (STOC '15) presented a deterministic algorithm with a
$2^{O(\sqrt{\log t\cdot\log\log n})}$ overhead in running time and the
additional assumption that a small superset of the output is given; this
assumption was later removed by Bringmann and Nakos (ICALP '21).
In this paper we present the first deterministic near-linear-time algorithm
for computing sparse nonnegative convolutions. This immediately gives improved
deterministic algorithms for the state-of-the-art of output-sensitive Subset
Sum, block-mass pattern matching, $N$-fold Boolean convolution, and others,
matching up to log-factors the fastest known randomized algorithms for these
problems. Our algorithm is a blend of algebraic and combinatorial ideas and
techniques.
Additionally, we provide two fast Las Vegas algorithms for computing sparse
nonnegative convolutions. In particular, we present a simple $O(t\log^2t)$ time
algorithm, which is an accessible alternative to Cole and Hariharan's
algorithm. We further refine this new algorithm to run in Las Vegas time
$O(t\log t\cdot\log\log t)$, matching the running time of the dense case apart
from the $\log\log t$ factor.
