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

DOI10.1145/2698587zbMath1347.68164OpenAlexW1663218918WikidataQ130924902 ScholiaQ130924902MaRDI QIDQ2828234

Andrey Utis, Aravind Srinivasan, William I. Gasarch, Andris Ambainis

Publication date: 24 October 2016

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2698587

zbMATH Keywords

Hamming distancecommunication complexity

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum algorithms and complexity in the theory of computing (68Q12)

Cites Work

• Unnamed Item
• Unnamed Item
• Zeros of generalized Krawtchouk polynomials
• The communication complexity of the Hamming distance problem
• Quantum communication and complexity.
• On the power of quantum fingerprinting
• Communication Complexity of Computing the Hamming Distance
• Interactive Communication of Balanced Distributions and of Correlated Files
• Communication via one- and two-particle operators on Einstein-Podolsky-Rosen states
• Communication Complexity

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