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?

  • 1
    $\begingroup$ Could you provide a pointer to an instance of the fragment methods you refer to? $\endgroup$ Apr 10, 2013 at 21:20
  • $\begingroup$ "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 $\endgroup$ Apr 11, 2013 at 15:26
  • $\begingroup$ 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. $\endgroup$ Apr 11, 2013 at 15:56
  • $\begingroup$ @AndrásSalamon fair enough. i was addressing the "are there other powerful methods" bit. $\endgroup$ Apr 13, 2013 at 9:49


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.