Matrix discrepancy and the log-rank conjecture

Given an $m\times n$ binary matrix $M$ with $\mathrm{\mid }M\mathrm{\mid }=p\cdot mn$ (where $\mathrm{\mid }M\mathrm{\mid }$ denotes the number of 1 entries), define the discrepancy of $M$ as $disc(M)={\displaystyle \underset{X\subset [m],Y\subset [n]}{\max }\mid \mathrm{\mid }M[X\times Y]\mathrm{\mid }-p\mathrm{\mid }X\mathrm{\mid }\cdot \mathrm{\mid }Y\mathrm{\mid }\mid }$. Using semidefinite programming and spectral techniques, we prove that if $rank(M)\le r$ and $p\le 1\mathrm{/}2$, then $$disc(M)\ge \mathrm{\Omega }(mn)\cdot \min \{p,\frac{p^{1\mathrm{/}2}}{\sqrt{r}}\}\mathrm{.}$$ We use this result to obtain a modest improvement of Lovett’s best known upper bound on the log-rank conjecture. We prove that any $m\times n$ binary matrix $M$ of rank at most $r$ contains an $(m\cdot 2^{-O(\sqrt{r})})\times (n\cdot 2^{-O(\sqrt{r})})$ sized all-1 or all-0 submatrix, which implies that the deterministic communication complexity of any Boolean function of rank $r$ is at most $O(\sqrt{r})$.