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 complexityTalagrand's concentration inequalitygap Hamming distance

Mathematics Subject Classification ID

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

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

(25)

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

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)