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

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

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

CC BY-SA 3.0
2012-04-20T17:37:39.950Z
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.
András Salamon
CC BY-SA 3.0
2012-04-21T05:28:58.377Z
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?
Noam
CC BY-SA 3.0
2012-04-25T01:18:17.230Z
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).
Marcos Villagra
CC BY-SA 3.0
2012-04-25T01:20:57.150Z
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.
Marcos Villagra
<cc.complexity-theory><co.combinatorics><linear-algebra><communication-complexity>
Lower Bound Methods in NonDet Communication Complexity
Jeigh
# Lower Bound Methods in NonDet Communication Complexity

(Asked by: username_0 on 2012-04-20)

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$ ?

**Tags:** cc.complexity-theory, co.combinatorics, linear-algebra, communication-complexity

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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?  
> **username_3**: 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).  
> **username_3**: just to make things clear, when I say positive-rank I mean what @username_2 said in his comment, U and V are non-negative. This is just my wording.  

---

## 0 answers

