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 nonnegative 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 an analogous result 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 complexity 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. We also show that our method yields an alternative simple proof of the equivalence between the approximate rank and the approximate μ norm, first shown by Lee and Shraibman.