 Author
 Date
 122012
 Title
 New bounds on the classical and quantum communication complexity of some graph properties
 Journal
 Leibniz International Proceedings in Informatics
 Volume
 18
 Pages (fromto)
 148159
 Document type
 Article
 Faculty
 Interfacultary Research Institutes
 Institute
 Institute for Logic, Language and Computation (ILLC)
 Abstract

We study the communication complexity of a number of graph properties where the edges of the graph G are distributed between Alice and Bob (i.e., each receives some of the edges as input). Our main results are: 1. An Omega(n) lower bound on the quantum communication complexity of deciding whether an nvertex graph G is connected, nearly matching the trivial classical upper bound of O(n log n) bits of communication. 2. A deterministic upper bound of O(n^{3/2} log n) bits for deciding if a bipartite graph contains a perfect matching, and a quantum lower bound of Omega(n) for this problem. 3. A Theta(n^2) bound for the randomized communication complexity of deciding if a graph has an Eulerian tour, and a Theta(n^{3/2}) bound for its quantum communication complexity. 4. The first two quantum lower bounds are obtained by exhibiting a reduction from the nbit Inner Product problem to these graph problems, which solves an open question of Babai, Frankl and Simon [Babai et al 1986]. The third quantum lower bound comes from recent results about the quantum communication complexity of composed functions. We also obtain essentially tight bounds for the quantum communication complexity of a few other problems, such as deciding if $G$ is trianglefree, or if G is bipartite, as well as computing the determinant of a distributed matrix.
 URL
 go to publisher's site
 Language
 English
 Note
 32nd International Conference on Foundations of Software Technology and Theoretical Computer Science : FSTTCS 2012, December
1517, 2012, Hyderabad, India
Editors: D. D'Souza, T. Kavitha, J. Radhakrishnan
ISBN 9783939897477  Permalink
 http://hdl.handle.net/11245/1.380261
 Downloads
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.