Lower Bounds on the Deterministic and Quantum Communication Complexities of Hamming-Distance Problems

DOI10.1007/11940128_63MaRDI QIDQ5459157zbMATH OpenOpenAlexFDO

Authors Aravind Srinivasan, Andrey Utis, Andris Ambainis, William Gasarch

Publication date 24 April 2008

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11940128_63

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum computation (81P68)

Recommendations

• Lower bounds on the deterministic and quantum communication complexity of Hamming-distance problems
• The communication complexity of the Hamming distance problem
• Lower Bounds for Quantum Communication Complexity
• Lower bound on expected communication cost of quantum Huffman coding
• Communication Complexity of Computing the Hamming Distance
• On a Problem Concerning the Quantum Hamming Bound for Impure Quantum Codes
• Near-optimal bounds on the bounded-round quantum communication complexity of disjointness
• The communication complexity of gap Hamming distance

Cited in

(5)

• Lower bounds on the deterministic and quantum communication complexity of Hamming-distance problems
• Generalizations of the distributed Deutsch-Jozsa promise problem
• Communication Complexity of Computing the Hamming Distance
• One-sided error communication complexity of gap Hamming distance
• The communication complexity of the Hamming distance problem

This page was built for publication: Lower Bounds on the Deterministic and Quantum Communication Complexities of Hamming-Distance Problems

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