A direct proof for Lovett's bound on the communication complexity of low rank matrices

Thomas Rothvoss

The log-rank conjecture in communication complexity suggests that the deterministic communication complexity of any Boolean rank-r function is bounded by polylog(r). Recently, majo…