Ivanyos, Gábor ;
Klauck, Hartmut ;
Lee, Troy ;
Santha, Miklos ;
de Wolf, Ronald
New bounds on the classical and quantum communication complexity of some graph properties
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.
BibTeX  Entry
@InProceedings{ivanyos_et_al:LIPIcs:2012:3852,
author = {G{\'a}bor Ivanyos and Hartmut Klauck and Troy Lee and Miklos Santha and Ronald de Wolf},
title = {{New bounds on the classical and quantum communication complexity of some graph properties}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) },
pages = {148159},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897477},
ISSN = {18688969},
year = {2012},
volume = {18},
editor = {Deepak D'Souza and Telikepalli Kavitha and Jaikumar Radhakrishnan},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2012/3852},
URN = {urn:nbn:de:0030drops38523},
doi = {http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2012.148},
annote = {Keywords: Graph properties, communication complexity, quantum communication}
}
Keywords: 

Graph properties, communication complexity, quantum communication 
Seminar: 

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)

Issue date: 

2012 
Date of publication: 

10.12.2012 