Matrix discrepancy and the log-rank conjecture

Given an $m\times n$ binary matrix M with $\left|M\right|=p·mn$ (where |M| denotes the number of 1 entries), define the discrepancy of M as $\text{disc}\left(M\right)={max}_{X\subset \left[m\right],Y\subset \left[n\right]}|\left|M[X\times Y]\right|-p\left|X\right|·\left|Y\right||$ . Using semidefinite programming and spectral techniques, we prove that if $\text{rank}\left(M\right)\le r$ and $p\le 1/2$ , then $\begin{array}{c}\text{disc}\left(M\right)\ge \Omega \left(mn\right)·min\left(p,,,\frac{p^{1/2}}{\sqrt{r}}\right).\end{array}$ 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·2^{-O\left(\sqrt{r}\right)})\times (n·2^{-O\left(\sqrt{r}\right)})$ 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\left(\sqrt{r}\right)$ .