Streaming Algorithms with One-Sided Estimation

We study the space complexity of randomized streaming algorithms that provide one-sided approximation guarantees; e.g., the algorithm always returns an overestimate of the function being computed, and with high probability, the estimate is not too far from the true answer. We also study algorithms which always provide underestimates.

We also give lower bounds for several one-sided estimators that match the deterministic space complexity, thus showing that to get a space-efficient solution, two-sided approximations are sometimes necessary. For some of these problems, including estimating the longest increasing sequence in a stream, and estimating the Earth Mover Distance, these are the first lower bounds for randomized algorithms of any kind.

We show that for several problems, including estimating the radius of the Minimum Enclosing Ball (MEB), one-sided estimation is possible. We provide a natural function for which the space for one-sided estimation is asymptotically less than the space required for deterministic algorithms, but more than what is required for general randomized algorithms.

What if an algorithm has a one-sided approximation from both sides? In this case, we show the problem has what we call a Las Vegas streaming algorithm. We show that even for two-pass algorithms, a quadratic improvement in space is possible and give a natural problem, counting non-isolated vertices in a graph, which achieves this separation.