Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming

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, for example:•Andoni’s $F_{p}$ estimation algorithm for constant $p \gt 2$ (ICASSP, 2017) assumes a random oracle, but achieves optimal space and constant update time. Using HashPRG’s time-space trade-off we eliminate the random oracle assumption while preserving the other properties. Previously no time-optimal derandomization was known. Using similar techniques, we give an algorithm for a relaxed version of $\ell_{p}$ sampling in a turnstile stream. Both of our algorithms use $\tilde{O}\left(d^{1-2 / p}\right)$ bits of space and have $O(1)$ update time.•For $0\lt p\lt2$, the $1 \pm \varepsilon$ approximate $F_{p}$ estimation algorithm of Kane et al., (STOC, 2011) uses an optimal $O\left(\varepsilon^{-2} \log d\right)$ bits of space but has an update time of $O\left(\log ^{2}(1 / \varepsilon) \log \log (1 / \varepsilon)\right)$. Using HashPRG, we show that if $1 / \sqrt{d} \leq \varepsilon \leq 1 / d^{c}$ for an arbitrarily small constant $c \gt 0$, then we can obtain a $1 \pm \varepsilon$ approximate $F_{p}$ estimation algorithm that uses the optimal $O\left(\varepsilon^{-2} \log d\right)$ bits of space and has an update time of $O(\log d)$ in the Word RAM model, which is more than a quadratic improvement in the update time. We obtain similar improvements for entropy estimation.•CountSketch, with the fine-grained error analysis of Minton and Price (SODA, 2014). For derandomization, they suggested a direct application of Nisan’s generator, yielding a logarithmic multiplicative space overhead. With HashPRG we obtain an efficient derandomization yielding the same asymptotic space as when assuming a random oracle. Our ability to obtain a time-efficient derandomization makes crucial use of HashPRG’s symmetry. We also give the first derandomization of a recent private version of CountSketch.For a d-dimensional vector x being updated in a turnstile stream, we show that $\|x\|_{\infty}$ can be estimated up to an additive error of $\varepsilon\|x\|_{2}$ using $O\left(\varepsilon^{-2} \log (1 / \varepsilon) \log d\right)$ bits of space. Additionally, the update time of this algorithm is $O(\log 1 / \varepsilon)$ 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\|_{\infty}=\Theta\left(\|x\|_{2}\right)$, we show that the lower bound can be broken by giving an algorithm that uses $O\left(\varepsilon^{-2} \log d\right)$ bits of space which approximates $\|x\|_{\infty}$ up to an additive error of $\varepsilon\|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 / \varepsilon)$ in the Word RAM model.