Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR19-006 | 4th March 2019 08:27

Upper Bounds on Communication in terms of Approximate Rank

RSS-Feed




Revision #1
Authors: Anna Gal, Ridwan Syed
Accepted on: 4th March 2019 08:27
Downloads: 815
Keywords: 


Abstract:

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 deterministic upper bound in terms of approximate rank is tight up to constant factors, and the dependence on discrepancy in our randomized upper bound is tight up to taking square-roots. Our results can be used to obtain lower bounds on approximate rank. We also obtain a strengthening of Newman's theorem with respect to approximate rank.



Changes to previous version:

Added some comments and clarifications.


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
Downloads: 1450
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint