# Seminar: November 19

## Shachar Lovett, University of California at San Diego

## Communication is bounded by root of rank

The log rank conjecture is one of the fundamental open problems in communication complexity. It speculates that if for a boolean f(x,y), its associated matrix M_{x,y}=f(x,y) has rank r (over the reals), then there exists a deterministic protocol computing f which uses only poly-log(r) bits of communication. There is a trivial protocol which uses r bits of communication, and further progress on this problem reduced it to O(r) bits [Kotlov-Lovasz'96, Kotlov '97] and more recently to O(r/log(r)) bits assuming a number theoretic conjecture [BenSasson-L-RonZewi'12]. In this work, we prove an (unconditional) upper bound of O(r^{1/2} log(r)) bits.