Discrete Lunch‎ > ‎

The Log-Rank conjecture I

posted Oct 19, 2013, 8:46 PM by Dirk Oliver Theis   [ updated Oct 19, 2013, 8:51 PM ]
Mon Sep 2: Dirk talked about the Log-Rank conjecture in Communication Complexity.
Or so he planned.
What he really did was explain the deterministic communication complexity dcc(M) of a 0/1-matrix M, and showed that
The Log-Rank conjecture is that dcc(M) is bounded from above by polylog( rk(M) ).
There are several combinatorial conjectures which are equivalent to the communication complexity one.  Those will be discussed in future Lunches.