2021/05/12 by Karl Bringmann, Bringmann, Karl, Nick Fischer +3 · 1 citation
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Algorithms #Sparse and Compressive Sensing Techniques #cs.CC #cs.DS
paper · pdf · doi:10.48550/arxiv.2105.05984
44 pages, appears in STOC 2021
openalex publication_date 2021/05/12 · arxiv created 2021/05/14 · arxiv updated 2021/05/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Computing the convolution A⋆ 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⋆ B uses the Fast Fourier Transform and runs in time O(nlog n). However, often A and B satisfy sparsity conditions, and hence one could hope for significant improvements. The ideal goal is an O(klog k)-time algorithm, where k is the number of non-zero elements in the output, i.e., the size of the support of A⋆ 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(klog2 n). The main result of this paper is the first O(klog 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(loglog 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.