Tell me more ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
up vote 3 down vote favorite

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?

share|improve this question
1  
Could you provide a pointer to an instance of the fragment methods you refer to? – András Salamon Apr 10 at 21:20
"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 people.cs.umass.edu/~mcgregor/papers/08-lis.pdf – Sasho Nikolov Apr 11 at 15:26
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 Apr 11 at 15:56
@AndrásSalamon fair enough. i was addressing the "are there other powerful methods" bit. – Sasho Nikolov Apr 13 at 9:49

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.