Before revision: Since every protocol using up to bits partitions into at most monochromatic rectangles, and each of these has rank at most 1, The log-rank conjecture states that is also upper-bounded by a polynomial in the log-rank: for some constant , The best known upper bound, due to Lovett, states that
After revision: Since every protocol using up to bits partitions into at most monochromatic rectangles, and each of these has rank at most 1, The log-rank conjecture states that is also upper-bounded by a polynomial in the log-rank: for some constant , Lovettproved the upper boundThis was improved by Sudakov and Tomon, who removed the logarithmic factor, showing thatThis is the best currently known upper bound.