Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR14-046 | 8th April 2014 14:02

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 be a nearly tight lower bound on the deterministic communication complexity. Our result indicates that proving the analogue for the randomized case, namely that the log approximate nonnegative rank is a nearly tight bound on randomized communication complexity, would imply the tightness of the information cost bound.
Another corollary of our result is the existence of a boolean function with a quasipolynomial gap between its approximate rank and approximate nonnegative rank.

ISSN 1433-8092 | Imprint