Abstract
We show that deterministic communication complexity can be superlogarithmic in the partition number of the associated communication matrix. We also obtain near-optimal deterministic lower bounds for the clique vs. independent set problem, which in particular yields new lower bounds for the log-rank conjecture. These results follow from a simple adaptation of a communication-to-query simulation theorem of Raz and McKenzie, together with lower bounds for the analogous query complexity classes.
Joint work with Mika Goos and Thomas Watson.