Communication Lower Bounds via Block Sensitivity

Communication Lower Bounds via Block Sensitivity - Toni Pitassi

Toni Pitassi
University of Toronto
November 11, 2013

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 S is a search problem with high critical block sensitivity, then the composed search problem (Sg) requires large randomized communication, where (Sg) is obtained from S by replacing the n input variables of S by copies of a suitable two-party function g. Our result also holds in the number-on-forehead (NOF) model. Our main theorem leads to the following new applications. First, we exhibit a monotone function on n variables whose monotone circuits require depth Ω(n/logn). Previously a bound of Ω(n) was known (Raz, Wigderson 1992). Secondly we prove new rank and tree-size lower lower bounds for semi-algebraic systems, including Lovasz-Schrijver and Lasserre proof systems. We also obtain the first size-space tradeoff results for the same family of semi-algebraic proof systems. This is joint work with Mika Göös.