Matrix discrepancy and the log-rank conjecture

Given an m× n m×n binary matrix M with |M|=p· mn |M|=p·mn (where | M | denotes the number of 1 entries), define the discrepancy of M as \,disc\,(M)= max X⊂ [m], Y⊂ [n] ||M[X× Y]|-p|X|· |Y| | 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 rank(M)≤r and p≤ 1/2 p≤1/2 , then aligned\,disc\,(M)≥ Ω (mn)· min \ p,p1/2√r\ .aligned disc(M)≥Ω(mn)·minp,p1/2r. 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 m×n binary matrix M of rank at most r contains an (m· 2-O(√r))× (n· 2-O(√r)) (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) O(r) .