The Relationship between Inner Product and Counting Cycles

TY - GEN

T1 - The Relationship between Inner Product and Counting Cycles

AU - Sun, Xiaoming

AU - Wang, Chengu

AU - Yu, Wei

N1 - Conference code: 10

PY - 2012

Y1 - 2012

N2 - 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 Ω˜((n−b)/(b−a)) when a≡b(mod2) . 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 Ω(nlogp(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.

AB - 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 Ω˜((n−b)/(b−a)) when a≡b(mod2) . 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 Ω(nlogp(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.

U2 - 10.1007/978-3-642-29344-3_54

DO - 10.1007/978-3-642-29344-3_54

M3 - Conference article

SN - 0302-9743

VL - 7256

SP - 643

EP - 654

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

T2 - 10th Latin American Theoretical Informatics Symposium

Y2 - 16 April 2012 through 20 April 2012

ER -