Title: Better Gap Hamming lower bounds via Better Round Elimination.

Speaker: Joshua Brody, Dartmouth College

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 an isoperimetric
inequalities.

Results in this talk are joint work with Amit Chakrabarti, Oded Regev, Thomas
Vidick, and Ronald de Wolf.