4
$\begingroup$

I have a very basic question about random bits in streaming. How could a streaming algorithm use them? Can the algorithm use the same random bit at the start of the execution and look at it again later? Or it serves a random source that once you look at it, you will get a random bit?

Sometimes it makes difference on the space when the algorithm have to store the random bits in memory and look at it later. Or, are they just equivalent?

$\endgroup$
  • $\begingroup$ You may want to check this thesis, in one of the chapters the author talks about use of the number of times randoms are used (IIRC). $\endgroup$ – Kaveh Nov 25 '11 at 18:46
  • $\begingroup$ A related question is on how to derandomize streaming algorithms - many of the answers there might be helpful: cstheory.stackexchange.com/questions/589/… $\endgroup$ – Suresh Venkat Nov 26 '11 at 7:04
6
$\begingroup$

If you want something more formal, you can think of a streaming algorithm as a Turing machine with read-once random bits tape and working tapes whose total size is polylogarithmically bounded. So, you can store and reuse random bits, as long as you don't exceed your polylog memory bound.

From algorithms design perspective, designing and even understanding a streaming algorithm is usually a two-step process. First think of the streaming algorithm as a RAM that can magically reuse random bits, i.e. has access to a random oracle. Actually there are some papers that do propose algorithms in this random oracle model. But usually, the next step is to try to make the algorithm work with hash families with bounded independence rather than a true random oracle. The seed for such families is logarithmic in size, so you can afford to store it. For some fine examples of this, just check out the classical paper of Alon, Matias and Szegedy. Another, heavier hammer to use is Nisan's pseudorandom number generator, which also allows reducing the number of random bits needed to be stored down to polylogarithmic (but larger than you usually get from bounded independence). For an example of using Nisan's generator, look at Indyk's use of the Cauchy distribution to approximate the $\ell_1$-norm of a stream. Both papers are classic and good read.

Refs: AMS: www.tau.ac.il/~nogaa/PDFS/amsz4.pdf

Indyk: people.csail.mit.edu/indyk/stream.ps

$\endgroup$
  • $\begingroup$ In fact, using Nisan's PRG is the only correct way to generically use randomness in streaming that I'm aware of (I'm excluding special cases like the Indyk example). $\endgroup$ – Suresh Venkat Nov 26 '11 at 7:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.