Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > APPROXIMATE NONNEGATIVE RANK:
Reports tagged with approximate nonnegative rank:
TR14-046 | 8th April 2014
Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff

#### Approximate Nonnegative Rank is Equivalent to the Smooth Rectangle Bound

We consider two known lower bounds on randomized communication complexity: The smooth rectangle bound and the logarithm of the approximate non-negative rank. Our main result is that they are the same up to a multiplicative constant and a small additive term.
The logarithm of the nonnegative rank is known to ... more >>>

TR18-176 | 26th October 2018
We construct a simple and total XOR function $F$ on $2n$ variables that has only $O(\sqrt{n})$ spectral norm, $O(n^2)$ approximate rank and $n^{O(\log n)}$ approximate nonnegative rank. We show it has polynomially large randomized bounded-error communication complexity of $\Omega(\sqrt{n})$. This yields the first exponential gap between the logarithm of the ... more >>>