2023/04/13 by Praneeth Kacham, Kacham, Praneeth, Rasmus Pagh +5
Computer Science · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Privacy-Preserving Technologies in Data
paper · pdf · doi:10.48550/arxiv.2304.06853
openalex publication_date 2023/04/13 · openalex created_date 2023/04/19 · openalex updated_date 2026/07/28
We revisit Nisan's classical pseudorandom generator (PRG) for space-bounded computation (STOC 1990) and its applications in streaming algorithms. We describe a new generator, HashPRG, that can be thought of as a symmetric version of Nisan's generator over larger alphabets. Our generator allows a trade-off between seed length and the time needed to compute a given block of the generator's output. HashPRG can be used to obtain derandomizations with much better update time and without sacrificing space for a large number of data stream algorithms, such as Fp estimation in the parameter regimes p > 2 and 0 < p < 2 and CountSketch with tight estimation guarantees as analyzed by Minton and Price (SODA 2014) which assumed access to a random oracle. We also show a recent analysis of Private CountSketch can be derandomized using our techniques. For a d-dimensional vector x being updated in a turnstile stream, we show that ‖x‖∞ can be estimated up to an additive error of ε‖x‖2 using O(ε-2log(1/ε)log d) bits of space. Additionally, the update time of this algorithm is O(log 1/ε) in the Word RAM model. We show that the space complexity of this algorithm is optimal up to constant factors. However, for vectors x with ‖x‖∞ = Θ(‖x‖2), we show that the lower bound can be broken by giving an algorithm that uses O(ε-2log d) bits of space which approximates ‖x‖∞ up to an additive error of ε‖x‖2. We use our aforementioned derandomization of the CountSketch data structure to obtain this algorithm, and using the time-space trade off of HashPRG, we show that the update time of this algorithm is also O(log 1/ε) in the Word RAM model.