Shaving Logs via Large Sieve Inequality: Faster Algorithms for Sparse Convolution and More

Abstract. In sparse convolution-type problems, a common technique is to hash the input integers modulo a random prime [Formula: see text] for some parameter [Formula: see text], 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 [Formula: see text] is [Formula: see text] rather than [Formula: see text]; (2) It is difficult to derandomize the choice of [Formula: see text]; 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 [Formula: see text]-time Las Vegas algorithm that computes the convolution [Formula: see text] of two nonnegative integer vectors [Formula: see text], where [Formula: see text] is the output sparsity [Formula: see text]. Moreover, our algorithm terminates in [Formula: see text] time with [Formula: see text] probability. This simultaneously improves the [Formula: see text]-time Las Vegas algorithm [Bringmann, Fischer, Nakos SODA’22] and the Monte Carlo [Formula: see text]-time algorithm with failure probability [Formula: see text] [Bringmann, Fischer, Nakos STOC’21]. Text-to-Pattern Hamming Distances: Given a length-[Formula: see text] pattern [Formula: see text] and a length-[Formula: see text] text [Formula: see text], we obtain a deterministic [Formula: see text]-time algorithm that exactly computes the Hamming distance between [Formula: see text] and every length-[Formula: see text] substring of [Formula: see text]. This improves the previous [Formula: see text]-time deterministic algorithm [Chan, Jin, Vassilevska Williams, Xu FOCS’23] and nearly matches their [Formula: see text]-time Las Vegas algorithm. Sparse General Convolution: For sparse convolution with possibly negative input, all previous approaches required [Formula: see text] time, where [Formula: see text] is the maximum of input and output sparsity, and an important question left open by [Bringmann, Fischer, Nakos STOC’21] is whether this can be improved. We make partial progress towards solving this question by giving a Monte Carlo [Formula: see text] time algorithm in the restricted case where the input vectors have length [Formula: see text] and polynomially bounded entries.