<p>The log of the partition number is a lower bound on the deterministic communication complexity and the square of the log of the partition number is an upper bound. In other words, if $CC$ is the communication complexity, then we know that $\log_2 p \leq CC \leq (\log_2 p)^2$: this is Theorem 2.11. in the Kushilevitz-Nisan monograph. It is an open problem whether $CC = \Theta(\log p)$, and the biggest known gap is a factor $2$.</p>

<p>So $p &lt; r^{\log^d r}$ for a constant $d$ implies that the communication complexity is at most $\log^{2d+2} r$. In other words there exists such a constant $d$ if and only if the log rank conjecture is true. I believe the best we know is $p &lt; r^{C\sqrt{r}}$ for a constant $C$, by <a href="http://eccc.hpi-web.de/report/2013/084/download" rel="nofollow">a recent result of Lovett</a>. </p>

CC BY-SA 3.0
2014-12-19T19:55:53.407Z
No it could still be the case that $p<r^{\log^dr}$ but deterministic complexity $q>r^{\log^dr}$.
Turbo
CC BY-SA 3.0
2014-12-19T20:00:12.040Z
Let the deterministic communication complexity be $\log_2 q$. Then $p \leq q \leq p^2$. So if $p < r^{\log^d r}$ then $q \leq r^{2\log^d r}$.
Sasho Nikolov
CC BY-SA 3.0
2014-12-19T20:05:21.690Z
makes sense I did not know the upper bound. What is a good way to see the upper bound?
Turbo
CC BY-SA 3.0
2014-12-19T20:15:05.803Z
Can we say anything about $\sigma$ bouding $p$? If $r<\sigma<2^{(\log_2r)^e}$ for some $e>0$ then it is true that$p<\sigma^{\log^d\sigma}$ since $r<\sigma$.
Turbo
CC BY-SA 3.0
2014-12-19T20:47:13.197Z
I am sorry I made a mistake, see my edit. A quasipolynomial bound on $p$ in terms of $r$ still is equivalent to the log rank conjecture, however.
Sasho Nikolov
CC BY-SA 3.0
2015-02-03T17:17:26.500Z
"the biggest known gap is a factor 2" is it from Kushilevitz Linial Ostrivsky's paper?
Turbo
CC BY-SA 3.0
2014-12-19T18:41:19.307Z
2014-12-19T20:58:32.437Z
2014-12-19T20:58:32.437Z
Sasho Nikolov
<p>Given matrix $M\in\{0,1\}^{n\times n}$, let the minimum number of monochromatic rectangles it can be partitioned be $p$. Let the positive rank of $M$ be $\sigma$ and the rank be $r$. Is it known either $$p&lt;r^{\log^dr}\mbox{ or }p&lt;\sigma^{\log^c\sigma}\mbox{ or }p&lt;(\sigma^{\log^c\sigma}r^{\log^dr})$$ hold true for some $c,d&gt;0$?</p>

<p>Can $p&lt;\sigma^{c}$ be true?</p>

<communication-complexity>
Partition Number of a Matrix
Turbo
# Partition Number of a Matrix

(Asked by: username_0 on 2014-12-19)

Given matrix $M\in\{0,1\}^{n\times n}$, let the minimum number of monochromatic rectangles it can be partitioned be $p$. Let the positive rank of $M$ be $\sigma$ and the rank be $r$. Is it known either $$p0$?

Can $p<\sigma^{c}$ be true?

**Tags:** communication-complexity


---

## 1 answers

### Answer by username_1 on 2014-12-19. Score: 4

The log of the partition number is a lower bound on the deterministic communication complexity and the square of the log of the partition number is an upper bound. In other words, if $CC$ is the communication complexity, then we know that $\log\_2 p \leq CC \leq (\log\_2 p)^2$: this is Theorem 2.11. in the Kushilevitz-Nisan monograph. It is an open problem whether $CC = \Theta(\log p)$, and the biggest known gap is a factor $2$.

So $p < r^{\log^d r}$ for a constant $d$ implies that the communication complexity is at most $\log^{2d+2} r$. In other words there exists such a constant $d$ if and only if the log rank conjecture is true. I believe the best we know is $p < r^{C\sqrt{r}}$ for a constant $C$, by [a recent result of Lovett](http://eccc.hpi-web.de/report/2013/084/download).

> **Comments:**
> **username_0**: No it could still be the case that $p<r^{\log^dr}$ but deterministic complexity $q>r^{\log^dr}$.  
> **username_1**: Let the deterministic communication complexity be $\log_2 q$. Then $p \leq q \leq p^2$. So if $p < r^{\log^d r}$ then $q \leq r^{2\log^d r}$.  
> **username_0**: makes sense I did not know the upper bound. What is a good way to see the upper bound?  
> **username_0**: Can we say anything about $\sigma$ bouding $p$? If $r<\sigma<2^{(\log_2r)^e}$ for some $e>0$ then it is true that$p<\sigma^{\log^d\sigma}$ since $r<\sigma$.  
> **username_1**: I am sorry I made a mistake, see my edit. A quasipolynomial bound on $p$ in terms of $r$ still is equivalent to the log rank conjecture, however.  
> **username_0**: "the biggest known gap is a factor 2" is it from Kushilevitz Linial Ostrivsky's paper?  

---

