Communication Complexity of Computing the Hamming Distance

DOI10.1137/0215065MaRDI QIDQ3756524zbMATH OpenOpenAlexFDO

Authors

Publication date 1986

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0215065

zbMATH Keywords

combinatorial extremal problemcommunication complexityHamming distancerandomized protocol

Mathematics Subject Classification ID

Theory of operating systems (68N25) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The communication complexity of the Hamming distance problem
• Lower bounds on the deterministic and quantum communication complexity of Hamming-distance problems
• The information complexity of Hamming distance
• Lower Bounds on the Deterministic and Quantum Communication Complexities of Hamming-Distance Problems
• The communication complexity of gap Hamming distance

Cited in

(19)

• Communication complexity of convex optimization
• A general 4-words inequality with consequences for 2-way communication complexity
• Still another rank determination of set intersection matrices with an application in communication complexity
• Communication complexity of sum-type functions invariant under translation
• Deterministic communication complexity of set intersection
• Lower bounds on the deterministic and quantum communication complexity of Hamming-distance problems
• The communication complexity of gap Hamming distance
• The information complexity of Hamming distance
• The one-way communication complexity of Hamming distance
• scientific article; zbMATH DE number 2162205 (Why is no real title available?)
• scientific article; zbMATH DE number 1445304 (Why is no real title available?)
• Communication complexity of statistical distance
• Communication complexity of statistical distance
• One-sided error communication complexity of gap Hamming distance
• Hamming Distance Completeness
• Lower Bounds on the Deterministic and Quantum Communication Complexities of Hamming-Distance Problems
• Ning Cai's work on communication complexity
• A two-family extremal problem in Hamming space
• The communication complexity of the Hamming distance problem

This page was built for publication: Communication Complexity of Computing the Hamming Distance

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