Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming

We revisit Nisan's classical pseudorandom generator (PRG) for space-boundedcomputation (STOC 1990) and its applications in streaming algorithms. Wedescribe a new generator, HashPRG, that can be thought of as a symmetricversion of Nisan's generator over larger alphabets. Our generator allows atrade-off between seed length and the time needed to compute a given block ofthe generator's output. HashPRG can be used to obtain derandomizations withmuch better update time and \emph{without sacrificing space} for a large numberof data stream algorithms, such as $F_p$ estimation in the parameter regimes $p> 2$ and $0 < p < 2$ and CountSketch with tight estimation guarantees asanalyzed by Minton and Price (SODA 2014) which assumed access to a randomoracle. We also show a recent analysis of Private CountSketch can bederandomized using our techniques. For a $d$-dimensional vector $x$ being updated in a turnstile stream, we showthat $\|x\|_{\infty}$ can be estimated up to an additive error of$\varepsilon\|x\|_{2}$ using $O(\varepsilon^{-2}\log(1/\varepsilon)\log d)$bits of space. Additionally, the update time of this algorithm is $O(\log1/\varepsilon)$ in the Word RAM model. We show that the space complexity ofthis algorithm is optimal up to constant factors. However, for vectors $x$ with$\|x\|_{\infty} = \Theta(\|x\|_{2})$, we show that the lower bound can bebroken by giving an algorithm that uses $O(\varepsilon^{-2}\log d)$ bits ofspace which approximates $\|x\|_{\infty}$ up to an additive error of$\varepsilon\|x\|_{2}$. We use our aforementioned derandomization of theCountSketch data structure to obtain this algorithm, and using the time-spacetrade off of HashPRG, we show that the update time of this algorithm is also$O(\log 1/\varepsilon)$ in the Word RAM model.