A Simple Las Vegas Algorithm for Sparse Nonnegative Convolution

Abstract

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)$ expected time. More generally, for every $0<\delta \le \frac{1}{2}$, the algorithm terminates within $O(t\log t\log \frac{1}{\delta })$ time with probability at least $1-\delta$. The algorithm uses dense convolution, linear hashing, and the length reduction of \cite{BFN22}. Its main ingredient is a carry-free representation of the indices as vectors of constant dimension $d$ whose coordinates have size $O(t/\log t)$. We can then take our hash function to be the inner product with a random element of ${\mathbb{F}}_p^d$ for a prime $p$ of size $\Omega (t/\log t)$: this preserves addition and gives collision probability exactly $1/p$, while identities regarding the moments of the vectors identify and recover the isolated terms as in \cite{BFN22}. Our expected running time matches that of Jin and Xu~\cite{JX24} while using substantially different tools and yielding a simpler algorithm. Note that their algorithm also terminates within $O(t\log t)$ time with probability at least $1-\frac{1}{t}$, while our tail bound is weaker.