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

DOI10.1137/120861072zbMath1259.68087arXiv1009.3460OpenAlexW1985526537MaRDI 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 boundscommunication complexitydata streamscorruptiongap-Hamming-distanceGaussian noise correlationgaussian noise correlation

Mathematics Subject Classification ID

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)

Sketching and Embedding are Equivalent for Norms ⋮ Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications ⋮ Interactive Information Complexity ⋮ The Cost of Fault Tolerance in Multi-Party Communication Complexity ⋮ Interactive Information Complexity ⋮ Anticoncentration and the Exact Gap-Hamming Problem ⋮ Towards Optimal Moment Estimation in Streaming and Distributed Models ⋮ Low correlation noise stability of symmetric sets ⋮ Symmetry of minimizers of a Gaussian isoperimetric problem ⋮ Communication complexity with small advantage ⋮ Towards Optimal Moment Estimation in Streaming and Distributed Models ⋮ The communication complexity of functions with large outputs ⋮ Communication and information complexity ⋮ Query Complexity of Sampling and Small Geometric Partitions ⋮ Query-to-Communication Lifting for BPP ⋮ Dimension-free bounds and structural results in communication complexity ⋮ Unnamed Item ⋮ A Simple Algorithm for Approximating the Text-To-Pattern Hamming Distance ⋮ Unnamed Item ⋮ Towards Unified Approximate Pattern Matching for Hamming and L_1 Distance ⋮ One-Sided Error Communication Complexity of Gap Hamming Distance. ⋮ Local minimality of the ball for the Gaussian perimeter ⋮ Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows. ⋮ Information lower bounds via self-reducibility ⋮ Non-interactive proofs of proximity ⋮ Property testing lower bounds via communication complexity ⋮ Unnamed Item ⋮ Rectangles Are Nonnegative Juntas ⋮ Fast size approximation of a radio network in beeping model ⋮ Unnamed Item ⋮ Approximating Approximate Pattern Matching ⋮ Lifting Theorems for Equality ⋮ The Complexity of Data Aggregation in Directed Networks ⋮ Two Party Distribution Testing: Communication and Security ⋮ Approximating the Size of a Radio Network in Beeping Model ⋮ Communication Complexity of Statistical Distance ⋮ Common Information, Noise Stability, and Their Extensions ⋮ Recent advances in text-to-pattern distance algorithms ⋮ Arthur-Merlin streaming complexity

This page was built for publication: An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance