Advertisement
Published in:
2012 | OriginalPaper | Chapter
The Relationship between Inner Product and Counting Cycles
Authors : Xiaoming Sun, Chengu Wang, Wei Yu
Published in: LATIN 2012: Theoretical Informatics
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Cycle-Counting
is the following communication complexity problem: Alice and Bob each holds a permutation of size
n
with the promise there will be either
a
cycles or
b
cycles in their product. They want to distinguish between these two cases by communicating a few bits. We show that the quantum/nondeterministic communication complexity is roughly
$\tilde \Omega((n-b)/(b-a))$
when
$a \equiv b \pmod 2$
. It is proved by reduction from a variant of the inner product problem over ℤ
m
. It constructs a bridge for various problems, including
In-Same-Cycle
[10],
One-Cycle
[14], and
Bipartiteness
on constant degree graph [9]. We also give space lower bounds in the streaming model for the
Connectivity
,
Bipartiteness
and
Girth
problems [7]. The inner product variant we used has a quantum lower bound of Ω(
n
log
p
(
m
)), where
p
(
m
) is the smallest prime factor of
m
. It implies that our lower bounds for
Cycle-Counting
and related problems still hold for quantum protocols, which was not known before this work.