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.