# Communication Lower Bounds via Block Sensitivity

 Computer Science/Discrete Mathematics Seminar I Topic: Communication Lower Bounds via Block Sensitivity Speaker: Toni Pitassi Affiliation: University of Toronto Date: Monday, November 11 Time/Room: 11:15am - 12:15pm/S-101 Video Link: https://video.ias.edu/csdm/2013/1111-ToniPitassi

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 $(S \circ g)$ requires large randomized communication, where $(S \circ g)$ 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 $\Omega(n/\log n)$. Previously a bound of $\Omega({\sqrt 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.