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

DOI10.1137/120861072zbMath1259.68087arXiv1009.3460MaRDI QIDQ4907584

Amit Chakrabarti, Oded Regev

Publication date: 4 February 2013

Published in: SIAM Journal on Computing, Proceedings of the forty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1009.3460

zbMATH Keywords

lower bounds; communication complexity; data streams; corruption; gap-Hamming-distance; Gaussian noise correlation; gaussian noise correlation

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

90B18: Communication networks in operations research

90C27: Combinatorial optimization

94A17: Measures of information, entropy

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

94A05: Communication theory

68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)