Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR19-006 | 17th January 2019 00:56

#### Upper Bounds on Communication in terms of Approximate Rank

TR19-006
Authors: Anna Gal, Ridwan Syed
Publication: 17th January 2019 00:58
We show that any Boolean function with approximate rank $r$ can be computed by bounded error quantum protocols without prior entanglement of complexity $O( \sqrt{r} \log r)$. In addition, we show that any Boolean function with approximate rank $r$ and discrepancy $\delta$ can be computed by deterministic protocols of complexity $O(r)$, and private coin bounded error randomized protocols of complexity $O((\frac{1}{\delta})^2 + \log r)$. Our results yield lower bounds on approximate rank. We also obtain a strengthening of Newman's theorem with respect to approximate rank.