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

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(logN/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].