Spring 2015

Deterministic Communication vs. Partition Number

Thursday, April 23rd, 2015 4:00 pm4:30 pm

Add to Calendar

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.