|
| | | | |
| | | |
| Stat |
Members: 3669
Articles: 2'599'751
Articles rated: 2609
13 March 2025 |
|
| | | | |
|
Article overview
| |
|
|
Separations in communication complexity using cheat sheets and information complexity | | Anurag Anshu
; Aleksandrs Belovs
; Shalev Ben-David
; Mika Göös
; Rahul Jain
; Robin Kothari
; Troy Lee
; Miklos Santha
; | | Date: |
4 May 2016 | | 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 also 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 G"o"os, 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. | | Source: | arXiv, 1605.1142 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
|
| |
|
|
|
REGISTER