A Simple Las Vegas Algorithm for Sparse Nonnegative Convolution
2026-08-17 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors present a randomized algorithm to efficiently compute the element-wise product (convolution) of two nonnegative vectors, focusing only on the parts where the result is nonzero. Their method runs in about t log t time on average, where t is the number of nonzero entries in the output. They use a clever hashing approach based on a vector representation of indices to avoid carries and reduce collisions, which helps them isolate and recover the correct values. This algorithm achieves similar performance to a recent method by Jin and Xu but uses different ideas and is simpler, although with a slightly weaker probability guarantee for the running time.
Las Vegas algorithmconvolutionnonnegative vectorssupport of a vectorhashingcarry-free representationfinite fieldexpected running timecomplexity analysisrandomized algorithms
Authors
Trevor Vaughn
Abstract
Let $A, B \in \mathbb{Z}_{\ge 0}^n$ be nonnegative vectors and let $t = |\operatorname{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 < δ\le \frac{1}{2}$, the algorithm terminates within $O(t \log t \log \frac{1}δ)$ time with probability at least $1 - δ$. 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 $Ω(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.