Approximate Nonnegative Rank is Equivalent to the Smooth Rectangle Bound

Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)1-25
Number of pages25
JournalComputational Complexity
Issue number1
StatePublished - Mar 11 2019

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Mathematics
  • Computational Theory and Mathematics
  • Computational Mathematics


  • 68Q17 Computational difficulty of problems
  • Communication complexity
  • Nonnegative rank
  • Smooth rectangle bound


Dive into the research topics of 'Approximate Nonnegative Rank is Equivalent to the Smooth Rectangle Bound'. Together they form a unique fingerprint.

Cite this