activity
20082022
most citedSublinear Communication Protocols for Multi-Party Pointer Jumping and a Related Lower Bound

7 citations · 14 across the 11 of their papers we have counts for

collaborators
Showing 2010Show all

1 paper · 1 filter

cs.CC2010

An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance

Amit Chakrabarti, Oded Regev

We prove an optimal lower bound on the randomized communication complexity of the much-studied Gap-Hamming-Distance problem. As a consequence, we obtain essentially optimal…