streaming algorithm that, with probability at least 1 − δ, computes a (1 ± )-approximation

Recall from last lecture the simple but useful model of one-way communication complexity. Alice has an input x ∈ {0, 1}a, Bob has an input y ∈ {0, 1}b, and the goal is to compute a Boolean function f: {0, 1}a × {0, 1}b → {0, 1} of the joint input (x,y). The players communicate as in Figure 1: Alice sends a message z to Bob as a function of x only (she doesn’t know Bob’s input y), and Bob has to decide the function f knowing only z and y (he doesn’t know Alice’s input x). The one-way communication complexity of f is the smallest number of bits communicated (in the worst case over (x,y)) of any protocol that computes f. We’ll sometimes consider deterministic protocols but are interested mostly in randomized protocols, which we’ll define more formally shortly. We motivated the one-way communication model through applications to streaming al-gorithms. Recall the data stream model, where a data stream x1,..., xm ∈ U of elements from a universe of n = |U | elements arrive one by one. The assumption is that there is insuf-ficient space to store all of the data, but we’d still like to compute useful statistics of it via a one-pass computation. Last lecture, we showed that very cool and non-trivial positive results are possible in this model. We presented a slick and low-space (O(−2(log n+ logm) log 1