Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming
summary
Introduces HashPRG, a symmetric Nisan-style PRG that trades seed length for block-evaluation time and is provably indistinguishable to algorithms using only εB bits of workspace. Uses this to derandomize CountSketch (and Private CountSketch) so the sketch needs only O(log n) words of stored counters while simulation runs in constant workspace per row. Gives an estimator for ‖x‖∞ with additive error ε‖x‖2 using O(ε−2 log(1/ε) log d) bits and O(log(1/ε)) update time; space is optimal up to constants and improves to O(ε−2 log d) when ‖x‖∞=Θ(‖x‖2).
AI-written summary · about
chapters (9)
- 0:00Pseudorandom hashing intro
- 2:34Tabulation to pseudorandom hashing
- 8:23Indistinguishability theorem
- 15:08Count sketch application
- 27:51Optimizing count sketch
- 39:23Space-time trade-offs
- 43:55Hash function symmetry
- 51:03Implementable hashing
- 55:40Closing & Q&A
related talks
01h 03mAdversarially Robust Streaming Algorithms
01h 30mRandom
30mKEYNOTE Building Succinct Arguments from Ideal Hash Functions
35mMulti-Party Distributed Point Functions
26mA Framework for Adversarial Streaming via Differential Privacy and Difference Estimators
32mOptimizing Pseudorandom Correlation Generators from LPN
14mlol im so random!
18mDifferentially Private Continual Releases of Streaming Frequency Moment Estimations