ECCC-Report TR14-046https://eccc.weizmann.ac.il/report/2014/046Comments and Revisions published for TR14-046en-usTue, 08 Apr 2014 15:13:36 +0300
Paper TR14-046
| Approximate Nonnegative Rank is Equivalent to the Smooth Rectangle Bound |
Shay Moran,
Gillat Kol,
Amir Shpilka,
Amir Yehudayoff
https://eccc.weizmann.ac.il/report/2014/046We 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.Tue, 08 Apr 2014 15:13:36 +0300https://eccc.weizmann.ac.il/report/2014/046