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?


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.

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

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.