Given an m×n binary matrix M with |M|=p·mn (where |M| denotes the number of 1 entries), define the discrepancy of M as disc(M)=maxX⊂[m],Y⊂[n]||M[X×Y]|-p|X|·|Y||. Using semidefinite programming and spectral techniques, we prove that if rank(M)≤r and p≤1/2, then (Formula presented.) 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×n binary matrix M of rank at most r contains an (m·2-O(r))×(n·2-O(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(r).