Mika Göös: Communication Complexity vs. Partition Numbers

ABSTRACT:

In communication complexity, perhaps the most basic observation is that a deterministic protocol computing a function F(x,y) partitions the communication matrix of F into 2^C monochromatic rectangles, where C is the number of bits exchanged between Alice and Bob. In other words, the logarithm of the *partition number* (least number of monochromatic rectangles needed to partition the communication matrix) is a lower bound on communication complexity.

We show that deterministic communication complexity can be superlogarithmic in the partition number. We also obtain near-optimal deterministic lower bounds for the related Clique vs. Independent Set problem (CIS; introduced by Yannakakis in 1988) that captures a one-sided variant of the partition number. In particular, this yields new lower bounds for the log-rank conjecture. We also provide some co-nondeterministic lower bounds for CIS, which has applications to the Alon--Saks--Seymour conjecture in graph theory.

To obtain the above results, we *cheat*: we study analogous questions in the easy-to-understand world of decision tree complexity, and then we "lift" these results over to communication complexity using a general simulation theorem.

Joint work with Toniann Pitassi and Thomas Watson. To appear at FOCS'15