2009.11.12 | Bjarke Hammersholt Roune

Speaker: Joshua Brody, Dartmouth College
joint work with Amit Chakrabarti, Ishay Haviv, Oded Regev, Thomas
Vidick, and Ronald de Wolf.

Abstract: The past fifteen years has seen an amazing burst of research
in streaming algorithms, starting with the famous paper by Alon,
Matias, and Szegedy. In particular, space-efficient algorithms are
possible for several functions, when you allow both randomness and
approximation. However, this comes at a price: most of the algorithms
pay a penalty in space that is quadratic with the approximation
factor.

In 2003, Woodruff and Indyk showed that this penalty was necessary in
the case of one-pass data streams, using a reduction from the one-way
complexity of the Gap Hamming problem. However, it has been a long
standing open problem whether the same lower bound applies to
multipass algorithms.

We extend this lower bound so it holds even when a constant number of
rounds of communication are allowed. As a result, we show that even
with O(1) passes, streaming algorithms must pay a high price for their
approximation. Our main technique combines a Round Elimination Lemma
with several isoperimetric inequalities.

See www.daimi.au.dk/~bjarke/compmath/ for more on CoMa talks. SK: 5211