A Multi-Round Communication Lower Bound for Gap Hamming and Some Consequences

Joshua Brody, Amit Chakrabarti

The Gap-Hamming-Distance problem arose in the context of proving space lower bounds for a number of key problems in the data stream model. In this problem, Alice and Bob have to de…