2
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ No it could still be the case that $p<r^{\log^dr}$ but deterministic complexity $q>r^{\log^dr}$. $\endgroup$
    – Turbo
    Commented Dec 19, 2014 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$
    – Sasho Nikolov
    Commented Dec 19, 2014 at 20:00
  • $\begingroup$ makes sense I did not know the upper bound. What is a good way to see the upper bound? $\endgroup$
    – Turbo
    Commented Dec 19, 2014 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$
    – Turbo
    Commented Dec 19, 2014 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$
    – Sasho Nikolov
    Commented Dec 19, 2014 at 20:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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