Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
Is communication complexity (CC) the only known approach for streaming algorithms lower bounds? Are there any other techniques, even if conditional lower bounds?
In general, are we satisfied with the progress achieved via CC? Or seeking alternative techniques (even if conditional) would be an interesting direction?
A recent result of Li, Nguyen, and Woodruff shows that for any streaming algorithm in the turnstile model (where the stream consists of insertions and deletions of elements) there exists an algorithm that works by only maintaining a linear sketch and uses only slightly more space. So to prove a space lower bound in the turnstile model it is (up to some logarithmic factors) enough to prove a space lower bound for linear sketches. These can be easier to prove, for example by proving a communication lower bound in the simultaneous communication model rather than in the one-way model, or by more directly working with the linear structure of the sketch: check the paper for a lower bound on the space complexity of frequency moments proved this way.
While not new, (and depending on what you consider to be "streaming algorithms"), a standard lower bound technique is picking a (as large as possible) set of inputs, and proving that each has to lead the algorithm to a distinct memory configuration. The implied lower bound is then the log of the number of such inputs.
For example, Datar et al. showed (Section 3) an $\Omega(\epsilon^{-1}\log^2 N\epsilon)$ lower bound for computing a $(1+\epsilon)$-approximation for the number of ones in the last $N$ bits of a binary stream.
