The information complexity of Hamming distance

DOI10.4230/LIPICS.APPROX-RANDOM.2014.465MaRDI QIDQ2969639zbMATH OpenOpenAlexFDO

Authors Eric Blais, Joshua Brody, Badih Ghazi

Publication date 22 March 2017

Full work available at URL http://people.csail.mit.edu/badih/papers/inf_comp_hd.pdf

zbMATH Keywords

communication complexityHamming distanceinformation complexity

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

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

Cited in

(4)

• The communication complexity of gap Hamming distance
• Communication Complexity of Computing the Hamming Distance
• Hamming Distance Completeness
• scientific article; zbMATH DE number 7758330 (Why is no real title available?)

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

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