Communication Lower Bounds via Critical Block Sensitivity

We use critical block sensitivity, a new complexity measure introduced by Huynh and Nordström [ STOC 2012, ACM, NY, 2012, pp. 233--248], 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 randomized two-party protocol solving a certain two-party lift of S requires Ω(b) bits of communication. Besides simplicity, our proof has the advantage of generalizing to the number-on-forehead multiparty setting. We combine these results with new critical block sensitivity lower bounds for Tseitin and pebbling search problems to obtain the following applications: Monotone circuit depth: We exhibit a monotone n-variable function in NP} whose monotone circuits require depth Ω(n/log n); previously, a bound of Ω(√n) was known [Raz and Wigderson, J. ACM, 39 (1992), pp. 736--744]. Moreover, we prove a Θ(√n) monotone depth bound for a function in monotone P. Proof complexity: We prove new rank lower bounds as well as obtain the first length-space lower bound for semialgebraic proof systems, including Lovász--Schrijver and Lasserre (sum over subsets systems. In particular, these results extend and simplify the works of Beame, Pitassi, and Segerlind [ SIAM J. Comput., 37 (2007), pp. 845--869] and Huynh and Nordström [ STOC 2012, ACM, NY, 2012, pp. 233--248].