2026-07-20T06:35:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3852 2024-03-06T10:34:31Z ddc:004 open_access

New bounds on the classical and quantum communication complexity of some graph properties Ivanyos, Gábor Klauck, Hartmut Lee, Troy Santha, Miklos de Wolf, Ronald Graph properties communication complexity quantum communication 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 n-vertex 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 n-bit 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 triangle-free, or if G is bipartite, as well as computing the determinant of a distributed matrix. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gábor Ivanyos and Hartmut Klauck and Troy Lee and Miklos Santha and Ronald de Wolf 2012 Is Part Of LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2012.148 urn:nbn:de:0030-drops-38523 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.148 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode