Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming

Abstract

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>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\left(1\right)$ update time.For $0<p<2$ , the $1\pm \epsilon$ approximate $F_p$ estimation algorithm of Kane et al., (STOC, 2011) uses an optimal $O\left({\epsilon }^{-2}\text{log}d\right)$ bits of space but has an update time of $O\left({\text{log}}^2\left(1/\epsilon \right)\text{log}\text{log}\left(1/\epsilon \right)\right)$ . Using HashPRG, we show that if $1/\sqrt{d}\le \epsilon \le 1/d^c$ for an arbitrarily small constant $c>0$ , then we can obtain a $1\pm \epsilon$ approximate $F_p$ estimation algorithm that uses the optimal $O\left({\epsilon }^{-2}\text{log}d\right)$ bits of space and has an update time of $O\left(\text{log}d\right)$ 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 ${\left(x\right)}_{\infty }$ can be estimated up to an additive error of $\epsilon \Vert x{\Vert }_2$ using $O\left({\epsilon }^{-2}\text{log}\left(1/\epsilon \right)\text{log}d\right)$ bits of space. Additionally, the update time of this algorithm is $O\left(\text{log}1/\epsilon \right)$ 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 ${\left(x\right)}_{\infty }=\Theta \left({\left(x\right)}_2\right)$ , we show that the lower bound can be broken by giving an algorithm that uses $O\left({\epsilon }^{-2}\text{log}d\right)$ bits of space which approximates $\Vert x{\Vert }_{\infty }$ up to an additive error of $\epsilon \Vert x{\Vert }_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\left(\text{log}1/\epsilon \right)$ in the Word RAM model.

Figure 1:

Overview of CountSketch guarantees with different kinds of random hash functions. For simplicity we focus on the case of $r=O\left(\text{log}d\right)$ repetitions and $d$-dimensional input vectors that contain $O\left(\text{log}d\right)$-bit integers such that the CountSketch itself (without hash functions) uses space $D=O\left(t\text{log}d\right)$ words. With pairwise independence we can only tightly bound the probability of exceeding error $\Delta ={‖{\text{tail}}_t\left(x\right)‖}_2/\sqrt{t}$, while the other hash functions allow us to bound the probability of smaller errors. Time bounds are for implementation on a Word RAM with word size $w=O\left(\text{log}d\right)$. Parameters with a particularly bad impact on space or time are highlighted in red color.