In a two-pass algorithm, the two steps may be implemented sequentially. A sampling sketch, like that of [1]}, is used to sample \(\sim \)  in the first pass. In the second pass, the algorithm knows the value of the sampled \(\) , so it maintains a sketch \((x_{\cdot , })\)  of size \(t\)  and a sketch \(^{\prime }(_{}[])\)  of size \(t^{\prime }\)  (to estimate \(\Pr _{}[]\) ) from which it can evaluate the random variable \(_{}\) . The counter-intuitive aspect is that, in this case, we will perform both steps in one-pass:
