<p>I am learning the methods for proving lower bounds on streaming algorithms using communication complexity.</p>

<p>My question is about a basic technique to prove lower bounds on streaming models using the reduction by giving each player in the communication game a fragment of the tape of Turing Machine whose sequential scan is bounded.The number of sequential scans is the number of passes. </p>

<p>We consider streaming algorithm as a one tape TM.</p>

<p>Is there some inherent limitations of this reduction using fragments of the tape?    </p>

<p>It seems that increasing of the number of passes deteriorates the efficiency of reductions and that we would not use this fragment methods to prove lower bounds on streaming models with many passes.</p>

<p>Are there other powerful methods which overcome the weakness of the fragment methods?</p>

CC BY-SA 3.0
2013-04-10T21:20:37.247Z
Could you provide a pointer to an instance of the fragment methods you refer to?
András Salamon
CC BY-SA 3.0
2013-04-11T15:26:39.650Z
"whose sequential scan is bounded" is mysterious to me. what is bounded? in any case, a single pass streaming algorithm corresponds to a one-way communication game. a $k$ pass streaming algorithm corresponds to a $k$ rounds of communication, and, yes, lower bounds on memory size for $k$ pass streaming have been proven via this reduction. for a discussion and a different (pass elimination) approach you can check http://people.cs.umass.edu/~mcgregor/papers/08-lis.pdf
Sasho Nikolov
CC BY-SA 3.0
2013-04-11T15:56:32.077Z
The Guha/McGregor paper shows that one can prove better results by looking at streaming directly, avoiding communication complexity reductions.  But I don't think their approach says anything about whether the limitations are inherent.
András Salamon
CC BY-SA 3.0
2013-04-13T09:49:52.287Z
@AndrásSalamon fair enough. i was addressing the "are there other powerful methods" bit.
Sasho Nikolov
<cc.complexity-theory><co.combinatorics><lower-bounds><communication-complexity><streaming>
Streaming Algorithm Lower Bounds by Communication Complexity
echuly
# Streaming Algorithm Lower Bounds by Communication Complexity

(Asked by: username_0 on 2013-04-08)

I am learning the methods for proving lower bounds on streaming algorithms using communication complexity.

My question is about a basic technique to prove lower bounds on streaming models using the reduction by giving each player in the communication game a fragment of the tape of Turing Machine whose sequential scan is bounded.The number of sequential scans is the number of passes.

We consider streaming algorithm as a one tape TM.

Is there some inherent limitations of this reduction using fragments of the tape?

It seems that increasing of the number of passes deteriorates the efficiency of reductions and that we would not use this fragment methods to prove lower bounds on streaming models with many passes.

Are there other powerful methods which overcome the weakness of the fragment methods?

**Tags:** cc.complexity-theory, co.combinatorics, lower-bounds, communication-complexity, streaming
> **Comments:**
> **username_1**: Could you provide a pointer to an instance of the fragment methods you refer to?  
> **username_2**: "whose sequential scan is bounded" is mysterious to me. what is bounded? in any case, a single pass streaming algorithm corresponds to a one-way communication game. a $k$ pass streaming algorithm corresponds to a $k$ rounds of communication, and, yes, lower bounds on memory size for $k$ pass streaming have been proven via this reduction. for a discussion and a different (pass elimination) approach you can check http://people.cs.umass.edu/~mcgregor/papers/08-lis.pdf  
> **username_1**: The Guha/McGregor paper shows that one can prove better results by looking at streaming directly, avoiding communication complexity reductions.  But I don't think their approach says anything about whether the limitations are inherent.  
> **username_2**: @AndrásSalamon fair enough. i was addressing the "are there other powerful methods" bit.  

---

## 0 answers

