Amit Chakrabarti, Oded Regev

We prove an optimal $\Omega(n)$ lower bound on the randomized

communication complexity of the much-studied

Gap-Hamming-Distance problem. As a consequence, we

obtain essentially optimal multi-pass space lower bounds in the

data stream model for a number of fundamental problems, including

the estimation of frequency moments.

The Gap-Hamming-Distance problem is a ... more >>>

Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff

We consider two known lower bounds on randomized communication complexity: The smooth rectangle bound and the logarithm of the approximate non-negative rank. Our main result is that they are the same up to a multiplicative constant and a small additive term.

The logarithm of the nonnegative rank is known to ...
more >>>