Communication Complexity of Computing the Hamming Distance

DOI10.1137/0215065zbMATH Open0619.68045OpenAlexW2028750115MaRDI QIDQ3756524FDOQ3756524

Author name not available (Why is that?)

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

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

zbMATH Keywords

Hamming distancecommunication complexityrandomized protocolcombinatorial extremal problem

Mathematics Subject Classification ID

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

Cited In (11)

• Lower Bounds on the Deterministic and Quantum Communication Complexities of Hamming-Distance Problems
• Communication complexity of convex optimization
• A general 4-words inequality with consequences for 2-way communication complexity
• Communication complexity of sum-type functions invariant under translation
• Still another rank determination of set intersection matrices with an application in communication complexity
• Lower bounds on the deterministic and quantum communication complexity of Hamming-distance problems
• A two-family extremal problem in Hamming space
• Title not available (Why is that?)
• Title not available (Why is that?)
• Deterministic communication complexity of set intersection
• The communication complexity of gap Hamming distance

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)