We use critical block sensitivity, a new complexity measure introduced by Huynh and Nordstrom (STOC 2012) to study the communication complexity of search problems. Our main result is a simple proof that if

# Communication Lower Bounds via Block Sensitivity

Toni Pitassi

University of Toronto

November 11, 2013