Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Approximate Rank:
TR10-086 | 17th May 2010
Henning Wunderlich

On a Theorem of Razborov

In an unpublished Russian manuscript Razborov proved that a matrix family with high
rigidity over a finite field would yield a language outside the polynomial hierarchy
in communication complexity.

We present an alternative proof that strengthens the original result in several ways.
In particular, we replace rigidity by the strictly ... more >>>

TR19-006 | 17th January 2019
Anna Gal, Ridwan Syed

Upper Bounds on Communication in terms of Approximate Rank

Revisions: 1

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 ... more >>>

ISSN 1433-8092 | Imprint