All reports by Author Aleksandrs Belovs:

__
TR16-072
| 4th May 2016
__

Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika G\"o{\"o}s, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha#### Separations in communication complexity using cheat sheets and information complexity

__
TR15-098
| 15th June 2015
__

Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs#### Separations in Query Complexity Based on Pointer Functions

Revisions: 2

Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika G\"o{\"o}s, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha

While exponential separations are known between quantum and randomized communication complexity for partial functions, e.g. Raz [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 ...
more >>>

Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs

In 1986, Saks and Wigderson conjectured that the largest separation between deterministic and zero-error randomized

query complexity for a total boolean function is given by the function $f$ on $n=2^k$ bits defined by a complete binary tree

of NAND gates of depth $k$, which achieves $R_0(f) = O(D(f)^{0.7537\ldots})$. ...
more >>>