Communication lower bounds via critical block sensitivity
Mika Göös, Toniann Pitassi · 2014
We use critical block sensitivity, a new complexity measure introduced by Huynh and Nordström (STOC 2012), to study the communication complexity of search problems. To begin, we give a simple new proof of the following central result of Huynh and Nordström: if S is a search problem with critical block sensitivity b, then every randomised two-party protocol solving a certain two-party lift of S requires Ω(b) bits of communication. Besides simplicity, our proof has the advantage of generalising to the multi-party setting. We combine these results with new critical block sensitivity lower bounds for Tseitin and Pebbling search problems to obtain the following applications.