Pseudorandom Hashing for Space-Bounded Computation with Applications in Streaming

Explore a comprehensive lecture on pseudorandom hashing for space-bounded computation and its applications in streaming algorithms. Delve into Mikkel Thorup's presentation at the Simons Institute, where he introduces HashPRG, a new generator that offers a symmetric version of Nisan's classical pseudorandom generator. Discover how this innovation allows for a trade-off between seed length and computation time for generator output blocks. Learn about the derandomization of various data stream algorithms, including Fp estimation and CountSketch, achieving better update times without compromising space efficiency. Examine the analysis of estimating the L-infinity norm of high-dimensional vectors in turnstile streams, including space complexity optimality and breakthrough algorithms for specific vector types. Gain insights into the practical applications of these techniques in the Word RAM model, offering efficient solutions for streaming algorithm challenges.