An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance
DOI10.1137/120861072zbMath1259.68087arXiv1009.3460OpenAlexW1985526537MaRDI QIDQ4907584
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
lower boundscommunication complexitydata streamscorruptiongap-Hamming-distanceGaussian noise correlationgaussian noise correlation
Analysis of algorithms and problem complexity (68Q25) Communication networks in operations research (90B18) Combinatorial optimization (90C27) Measures of information, entropy (94A17) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Communication theory (94A05) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items (39)
This page was built for publication: An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance