3
$\begingroup$

rank+($M$) is the minimum $r$ such that the following statement holds.

The statement : there exists matrices $U,V$ such that $M = UV$ and $U$ has $r$ columns and $V$ has $r$ rows.

Is rank+($M$) bounded from below by the rectangle covering bound for $M$ ?

Improve this question
$\endgroup$
4
  • $\begingroup$ You might wish to provide a bit more background or a pointer to an exposition of the rectangle method, like the Wikipedia article on communication complexity. Not everyone keeps the basics of communication complexity in cache. $\endgroup$ – András Salamon Apr 20 '12 at 17:37
  • 3
    $\begingroup$ You seem to be defining just the linear-algebra rank of the matrix M here -- is this your intention or are you trying to define the "positive-rank" which requires U and V to be non-negative? $\endgroup$ – Noam Apr 21 '12 at 5:28
  • $\begingroup$ Why NonDet appears in the title? As far as I know nondeterministic communication is not lower-bounded by rank or positive-rank (but it is upper-bounded by the positive-rank as showed by Yannakakis). Indeed, if you believe in the log-rank conjecture, then it cannot be lower-bounded by log-rank (because the nondeterministic communication can be exponentially more powerful). $\endgroup$ – Marcos Villagra Apr 25 '12 at 1:18
  • $\begingroup$ just to make things clear, when I say positive-rank I mean what @Noam said in his comment, U and V are non-negative. This is just my wording. $\endgroup$ – Marcos Villagra Apr 25 '12 at 1:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.