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…