Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution

Computing the convolution A∗B of two length-n integer vectors A, B is a core problem in several disciplines. It frequently comes up as a subroutine in various problem domains, e.g. 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, in many applications 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 and recently improved by Bringmann, Fischer and Nakos (STOC '21) in O(k log k) Monte Carlo time. Chan and Lewenstein (STOC '15) presented a deterministic algorithm with a 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 log2 t) time algorithm, which is an accessible alternative to Cole and Hariharan's algorithm. Subsequently, we further refine this new algorithm to run in Las Vegas time O(t log t · log log t), which matches the running time of the dense case apart from the log log t factor.