CS 229r: Algorithms for Big Data Fall 2015

In the last lecture we covered the distance to monotonicity (DTM) and longest increasing subse-quence (LIS) problems. In this lecture we will talk about how to prove space lower bounds for a variety of problems using communication complexity. 2 Space lower bounds We’re going to see some sophisticated techniques to prove space lower bounds. These are all proved via something called communication complexity. The problems we’re going to look at today are F0 (distinct elements)- specifically any algorithm that solves F0 within a factor of must use Ω(1/2 + log n) bits. We’re also going to discuss median, or randomized exact median, which requires Ω(n) space. Finally, we’ll talk about Fp or ‖x‖p, which requires Ω(n1−2/p) space for a 2-approximation. 2.1 2 player communication complexity Suppose we have Alice and Bob, and a function f: X×Y → {0, 1}. Alice gets x ∈ X, and Bob gets y ∈ Y. They want to compute f(x, y). Suppose that Alice starts the conversation. Suppose she sends a message m1 to Bob. Then Bob replies with m2, and so on. After k iterations, someone ca