Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR20-006 | 22nd January 2020 05:46

The Communication Complexity of the Exact Gap-Hamming Problem

RSS-Feed




TR20-006
Authors: Anup Rao, Amir Yehudayoff
Publication: 22nd January 2020 05:47
Downloads: 341
Keywords: 


Abstract:

We prove a sharp lower bound on the distributional communication complexity of the exact gap-hamming problem.



ISSN 1433-8092 | Imprint