2024/03/29 by Ce Jin, Jin, Ce, Yinzhan Xu +1 · 3 citations
Computer Science · Engineering · Mathematics · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Face and Expression Recognition #Sparse and Compressive Sensing Techniques #Statistical Methods and Inference
paper · pdf · doi:10.48550/arxiv.2403.20326
openalex publication_date 2024/03/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In sparse convolution-type problems, a common technique is to hash the input integers modulo a random prime p∈ [Q/2,Q] for some parameter Q, which reduces the range of the input integers while preserving their additive structure. However, this hash family suffers from two drawbacks, which led to bottlenecks in many state-of-the-art algorithms: (1) The collision probability of two elements from [N] is O((log N)/(Q)) rather than O((1)/(Q)); (2) It is difficult to derandomize the choice of p; known derandomization techniques lead to super-logarithmic overhead [Chan, Lewenstein STOC'15]. In this paper, we partially overcome these drawbacks in certain scenarios, via novel applications of the large sieve inequality from analytic number theory. Consequently, we obtain the following improved algorithms for various problems (in the standard word RAM model): Sparse Nonnegative Convolution: We obtain an O(tlog t)-time Las Vegas algorithm that computes the convolution A⋆ B of two nonnegative integer vectors A,B, where t is the output sparsity ‖A⋆ B‖0. Moreover, our algorithm terminates in O(tlog t) time with 1-1/poly(t) probability. Text-to-Pattern Hamming Distances: Given a length-m pattern P and a length-n text T, we obtain a deterministic O(n√(mlog log m))-time algorithm that exactly computes the Hamming distance between P and every length-m substring of T. Sparse General Convolution: We also give a Monte Carlo O(tlog t) time algorithm for sparse convolution with possibly negative input in the restricted case where the length N of the input vectors satisfies N≤ t1.99.