Computer Science/Discrete Mathematics Seminar I

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.