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

From MaRDI portal
Publication:4907584

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




Related Items (39)

Sketching and Embedding are Equivalent for NormsLower Bounds on Information Complexity via Zero-Communication Protocols and ApplicationsInteractive Information ComplexityThe Cost of Fault Tolerance in Multi-Party Communication ComplexityInteractive Information ComplexityAnticoncentration and the Exact Gap-Hamming ProblemTowards Optimal Moment Estimation in Streaming and Distributed ModelsLow correlation noise stability of symmetric setsSymmetry of minimizers of a Gaussian isoperimetric problemCommunication complexity with small advantageTowards Optimal Moment Estimation in Streaming and Distributed ModelsThe communication complexity of functions with large outputsCommunication and information complexityQuery Complexity of Sampling and Small Geometric PartitionsQuery-to-Communication Lifting for BPPDimension-free bounds and structural results in communication complexityUnnamed ItemA Simple Algorithm for Approximating the Text-To-Pattern Hamming DistanceUnnamed ItemTowards Unified Approximate Pattern Matching for Hamming and L_1 DistanceOne-Sided Error Communication Complexity of Gap Hamming Distance.Local minimality of the ball for the Gaussian perimeterNearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows.Information lower bounds via self-reducibilityNon-interactive proofs of proximityProperty testing lower bounds via communication complexityUnnamed ItemRectangles Are Nonnegative JuntasFast size approximation of a radio network in beeping modelUnnamed ItemApproximating Approximate Pattern MatchingLifting Theorems for EqualityThe Complexity of Data Aggregation in Directed NetworksTwo Party Distribution Testing: Communication and SecurityApproximating the Size of a Radio Network in Beeping ModelCommunication Complexity of Statistical DistanceCommon Information, Noise Stability, and Their ExtensionsRecent advances in text-to-pattern distance algorithmsArthur-Merlin streaming complexity




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