Paper Info
Title
Separations in Communication Complexity Using Cheat Sheets and Information Complexity
Abstract
While exponential separations are known between quantum and randomized communication complexity for partial functions (Raz, STOC 1999), the best known separation between these measures for a total function is quadratic, witnessed by the disjointness function. We give the first super-quadratic separation between quantum and randomized communication complexity for a total function, giving an example exhibiting a power 2.5 gap. We further present a 1.5 power separation between exact quantum and randomized communication complexity, improving on the previous ≈ 1.15 separation by Ambainis (STOC 2013). Finally, we present a nearly optimal quadratic separation between randomized communication complexity and the logarithm of the partition number, improving upon the previous best power 1.5 separation due to Goos, Jayram, Pitassi, and Watson. Our results are the communication analogues of separations in query complexity proved using the recent cheat sheet framework of Aaronson, Ben-David, and Kothari (STOC 2016). Our main technical results are randomized communication and information complexity lower bounds for a family of functions, called lookup functions, that generalize and port the cheat sheet framework to communication complexity.
Year
DOI
Venue
2016
10.1109/FOCS.2016.66
2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)
Keywords
DocType
Volume
communication complexity,randomized algorithms,quantum algorithms
Journal
abs/1605.01142
ISSN
ISBN
Citations 
0272-5428
978-1-5090-3934-0
7
PageRank 
References 
Authors
0.50
20
8
Name
Order
Citations
PageRank
Anurag Anshu14314.24
Aleksandrs Belovs213114.50
Shalev Ben-David3638.92
Mika Göös420319.55
Rahul Jain578471.51
Robin Kothari619621.05
Troy Lee727628.96
Miklós Sántha8967.95