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 thatThe Log-Rank conjecture is that dcc There are several combinatorial conjectures which are equivalent to the communication complexity one. Those will be discussed in future Lunches.(M) is bounded from above by polylog( rk(M) ). |

Discrete Lunch >