Deterministic Communication vs. Partition Number

We show that deterministic communication complexity can be super logarithmic 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. All these results follow from a simple adaptation of a communication-to-query simulation theorem of Raz and McKenzie (Combinatorica 1999) together with lower bounds for the analogous query complexity questions.

Authors

• Mika Göös
• Toniann Pitassi
• Thomas Watson 0001

Keywords

• Decision trees
• Complexity theory
• Upper bound
• Protocols
• Yttrium
• Boolean functions
• Computer science
• Deterministic Communication
• Lower Bound
• Complex Communication
• Maximum Independent Set
• Unambiguous
• Decision Tree
• Tree Nodes
• Communication Protocol
• Simulated Algorithm
• Coordinate Values
• Search Problem
• Left Node
• Boolean Function
• Input Bits
• Key Lemma