# Partition Number of a Matrix

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<r^{\log^dr}\mbox{ or }p<\sigma^{\log^c\sigma}\mbox{ or }p<(\sigma^{\log^c\sigma}r^{\log^dr})$$ hold true for some $c,d>0$?

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

## 1 Answer

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.

• No it could still be the case that $p<r^{\log^dr}$ but deterministic complexity $q>r^{\log^dr}$.
– Mr.
Dec 19 '14 at 19:55
• 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}$. Dec 19 '14 at 20:00
• makes sense I did not know the upper bound. What is a good way to see the upper bound?
– Mr.
Dec 19 '14 at 20:05
• 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$.
– Mr.
Dec 19 '14 at 20:15
• 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. Dec 19 '14 at 20:47