A Simple Las Vegas Algorithm for Sparse Nonnegative Convolution

Trevor Vaughn

Let $A,B\in {\mathbb{Z}}_{\ge 0}^n$ be nonnegative vectors and let $t=|\mathrm{supp}(A\star B)|$. We give a Las Vegas algorithm that computes $A\star B$ in $O(t\log t)$…