<p>A recent <a href="http://www.cs.princeton.edu/~hlnguyen/papers/lnw14b.pdf" rel="nofollow">result of Li, Nguyen, and Woodruff</a> 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.</p>

CC BY-SA 3.0
2015-06-09T19:16:48.543Z
2015-06-09T19:16:48.543Z
Sasho Nikolov
<p>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.</p>

<p>For example, <a href="http://ilpubs.stanford.edu/504/1/2001-34.pdf" rel="nofollow">Datar et al.</a> 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. </p>

CC BY-SA 3.0
2015-06-09T19:04:29.610Z
This is really a simple communication lower bound in disguise.
Sasho Nikolov
CC BY-SA 3.0
2015-06-08T13:44:22.627Z
2015-06-09T09:38:42.067Z
2015-06-09T09:38:42.067Z
R B
<p>Is communication complexity (CC) the only known approach for streaming algorithms lower bounds? Are there any other techniques, even if <em>conditional</em> lower bounds?</p>

<p>In general, are we satisfied with the progress achieved via CC? Or seeking alternative techniques (even if conditional) would be an interesting direction? </p>

<lower-bounds><streaming-algorithms><proof-techniques>
New Space Lower-Bound Techniques for Streaming Algorithms
user34384
# New Space Lower-Bound Techniques for Streaming Algorithms

(Asked by: username_0 on 2015-06-08)

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?

**Tags:** lower-bounds, streaming-algorithms, proof-techniques

---

## 2 answers

### Answer by username_1 on 2015-06-09. Score: 4

A recent [result of Li, Nguyen, and Woodruff](http://www.cs.princeton.edu/~hlnguyen/papers/lnw14b.pdf) 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.


---

### Answer by username_2 on 2015-06-08. Score: 3

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.](http://ilpubs.stanford.edu/504/1/2001-34.pdf) 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.

> **Comments:**
> **username_1**: This is really a simple communication lower bound in disguise.  

---

