Communication Lower Bounds via Critical Block Sensitivity

Abstract:

In the basic model of communication complexity, two players, Alice and Bob, receive some inputs x and y, respectively. Their goal is to engage in a dialogue over a shared communication channel in order to compute some joint function f(x,y) of the inputs. How many bits must be transmitted between the players?

In addition to the obvious applications (communication networks, distributed systems), communication complexity lower bounds imply impossibility results in many other concrete computational models like boolean circuits, proof systems (e.g., run-time lower bounds for SAT algorithms), Turing machines (e.g., time--space trade-offs), property testing, extended formulations for LPs, streaming algorithms, etc.

In this talk, I present some new lower bounds on the communication complexity of search problems. Our approach is based on a new complexity measure called "critical block sensitivity" that was recently introduced by Huynh and Nordström (STOC 2012). As concrete applications, we obtain the following:

(1) Monotone Circuit Depth: 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 and Wigderson, JACM 1992). Moreover, we prove a tight Theta(sqrt(n)) monotone depth bound for a function in monotone P. This implies an average-case hierarchy theorem within monotone P similar to a result of Filmus et al. (FOCS 2013).

(2) Proof Complexity: We prove new rank lower bounds as well as obtain the first length--space lower bounds for semi-algebraic proof systems, including Lovasz--Schrijver and Lasserre (SOS) systems. In particular, these results extend and simplify the works of Beame et al. (SICOMP 2007) and Huynh and Nordström.

This is joint work with Toniann Pitassi. A preprint is available at http://arxiv.org/abs/1311.2355.

About the speaker:

Mika Göös (http://www.cs.utoronto.ca/~mgoos/) is a PhD student at the University of Toronto. Previously, Mika worked in the "New Paradigms in Computing" group at HIIT.