# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution

##### MPS-Authors

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

arXiv:2107.07625.pdf

(Preprint), 617KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Bringmann, K., Fischer, N., & Nakos, V. (2021). Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution. Retrieved from https://arxiv.org/abs/2107.07625.

Cite as: https://hdl.handle.net/21.11116/0000-0009-B454-D

##### 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.

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.