Sparse nonnegative convolution is equivalent to dense nonnegative convolution

Computing the convolution A ⋆ B of two length- n vectors A , B is an ubiquitous computational primitive, with applications in a variety of disciplines. Within theoretical computer science, 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 (FFT) and runs in time O ( n log n ).

Authors

• Karl Bringmann
• Nick Fischer
• Vasileios Nakos

Keywords

• Convolution
• FFT
• Linear Hashing
• Sparsity