7 citations · 17 across the 8 of their papers we have counts for
Showing 2009Show all
2 papers · 1 filter
cs.CC2009
Better Gap-Hamming Lower Bounds via Better Round Elimination
Joshua Brody, Amit Chakrabarti, Oded Regev +2
Gap Hamming Distance is a well-studied problem in communication complexity, in which Alice and Bob have to decide whether the Hamming distance between their respective n-bit inputs…
cs.CC2009★ 1 cited
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…