 Author
 Year
 2015
 Title
 Round Elimination in Exact Communication Complexity
 Journal
 Leibniz International Proceedings in Informatics
 Volume
 44
 Pages (fromto)
 206225
 Document type
 Article
 Faculty
 Interfacultary Research Institutes
 Institute
 Institute for Logic, Language and Computation (ILLC)
 Abstract

We study two basic graph parameters, the chromatic number and the orthogonal rank, in the context of classical and quantum exact communication complexity. In particular, we consider two types of communication problems that we call promise equality and list problems. For both of these, it was already known that the oneround classical and oneround quantum complexities are characterized by the chromatic number and orthogonal rank of a certain graph, respectively. In a promise equality problem, Alice and Bob must decide if their inputs are equal or not. We prove that classical protocols for such problems can always be reduced to oneround protocols with no extra communication. In contrast, we give an explicit instance of a promise problem that exhibits an exponential gap between the one and tworound exact quantum communication complexities. Whereas the chromatic number thus captures the complete complexity of promise equality problems, the hierarchy of "quantum chromatic numbers" (starting with the orthogonal rank) giving the quantum communication complexity for every fixed number of communication rounds thus turns out to enjoy a much richer structure. In a list problem, Bob gets a subset of some finite universe, Alice gets an element from Bob's subset, and their goal is for Bob to learn which element Alice was given. The best general lower bound (due to Orlitsky) and upper bound (due to Naor, Orlitsky, and Shor) on the classical communication complexity of such problems differ only by a constant factor. We exhibit an example showing that, somewhat surprisingly, the fourround protocol used in the bound of Naor et al. can in fact be optimal. Finally, we pose a conjecture on the orthogonality rank of a certain graph whose truth would imply an intriguing impossibility of round elimination in quantum protocols for list problems, something that works trivially in the classical case.
 URL
 go to publisher's site
 Language
 English
 Note
 Proceedings title: 10th Conference on the Theory of Quantum Computation, Communication and Cryptography: TQC’15, May 2022,
2015, Brussels, Belgium
Publisher: Schloss Dagstuhl  LeibnizZentrum für Informatik
Place of publication: Wadern
ISBN: 9783939897965
Editors: S. Beigi, R. König  Permalink
 http://hdl.handle.net/11245/1.526546
Disclaimer/Complaints regulations
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.