The communication complexity of gap Hamming distance

DOI10.4086/TOC.2012.V008A008MaRDI QIDQ2913808zbMATH OpenOpenAlexFDO

Authors Alexander A. Sherstov

Publication date 27 September 2012

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2012.v008a008

zbMATH Keywords

communication complexitygap Hamming distanceTalagrand's concentration inequality

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The communication complexity of the Hamming distance problem
• Communication Complexity of Computing the Hamming Distance
• One-sided error communication complexity of gap Hamming distance
• The one-way communication complexity of Hamming distance
• The information complexity of Hamming distance
• Communication complexity of statistical distance
• Communication complexity of statistical distance
• The intractability of computing the Hamming distance

Cites work

• On the distributional complexity of disjointness

Cited in

(28)

• Communication complexity with small advantage
• Arthur-Merlin streaming complexity
• Low correlation noise stability of symmetric sets
• Lower bounds on the deterministic and quantum communication complexity of Hamming-distance problems
• The information complexity of Hamming distance
• The one-way communication complexity of Hamming distance
• Lower bounds on information complexity via zero-communication protocols and applications
• Communication Complexity of Computing the Hamming Distance
• Sketching and embedding are equivalent for norms
• Interactive information complexity
• Communication complexity of statistical distance
• Communication complexity of statistical distance
• One-sided error communication complexity of gap Hamming distance
• Anticoncentration and the Exact Gap-Hamming Problem
• Lifting Theorems for Equality
• Two Party Distribution Testing: Communication and Security
• Query-to-communication lifting for BPP
• scientific article; zbMATH DE number 7250149 (Why is no real title available?)
• scientific article; zbMATH DE number 6292622 (Why is no real title available?)
• Lower Bounds on the Deterministic and Quantum Communication Complexities of Hamming-Distance Problems
• Rectangles are nonnegative juntas
• The communication complexity of functions with large outputs
• Communication and information complexity
• A Borsuk-Ulam lower bound for sign-rank and its applications
• Lower bounds for semi-adaptive data structures via corruption
• Quantum and classical communication complexity of permutation-invariant functions
• Sketching approximability of all finite CSPs
• The communication complexity of the Hamming distance problem

This page was built for publication: The communication complexity of gap Hamming distance

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2913808)