The topic of this workshop is hardness escalation, a growing research area whereby lower bounds and separations in communication complexity are obtained by developing “simulation theorems”. The basic idea of a simulation theorem is to start with a simple ‘one-party’ function and “lift it” to a multi-party setting via function composition; as it turns out in many cases, the communication complexity of the new function can be characterized by the the query complexity of the original function. In query complexity, the objects of study are decision trees, perhaps the simplest, most basic model of computation. A simulation theorem thus essentially shows that the optimal communication protocol for the composed function is essentially the trivial one which mimics the decision tree protocol.
These simulation theorems have introduced new tools into complexity theory, and have led to the resolution of many open problems including: graph theory, combinatorial optimization, circuit complexity and cryptography, proof complexity, game theory, and communication complexity. Moreover the field has led to a revival of query complexity, with new techniques leading to the resolution of some longstanding open problems.
The goal of the workshop is to present a broad introduction to the area as well as highlight the recent developments.
Mika Goos, Robin Kothari, James Lee, Prasad Raghavendra, Robert Robere, Sasha Sherstov, Thomas Watson
The topic of this workshop is a set of powerful tools that translate query complexity lower bounds to corresponding communication complexity lower bounds. In recent years, these so-called lifting theorems have yielded a wide array of applications. In this talk, we will provide a tutorial introduction to the subject of query-to-communication lifting, and survey the known applications and recently-developed techniques for proving lifting theorems.
Query complexity is an old and well-studied model of computation that occupies a Goldilocks zone within computational models. It is simple enough that we can prove interesting results, and yet natural problems from 45 years ago remain unsolved.
I’ll provide a broad overview of the field, including complexity measures studied, the relations between them, and lower bound techniques. I’ll end with a survey of recent results, especially those with relevance to communication complexity and query-to-communication lifting theorems.
The LP Extension complexity of a polytope is size of the smallest linear program that represents the polytope after a projection. An analogous notion can be defined for semidefinite program. The model of extension complexity introduced by Yannakakis captures a large body of algorithms based on linear and semidefinite programming relaxations. Yannakakis showed that the LP extension complexity of a polytope is exactly characterized by the non-negative rank of an associated slack matrix, thereby connecting the model to notions in communication complexity.
Recent works have shown generic lifting theorems that lift lower bounds on conical-junta degree and sum-of-squares degree to corresponding lower bounds on LPs and SDPs respectively. In this talk, we will survey the extension complexity model, non-negative rank characterization and the lifting theorems in the model.
For any unsatisfiable CNF formula F that is hard to refute in the Resolution proof system, we show that a "lifted" two-party version of F is hard to refute in any proof system whose lines are computed by efficient communication protocols---or, equivalently, that a monotone function associated with F has large monotone circuit complexity. Our result extends to real monotone circuits, which yields new lower bounds for the Cutting Planes proof system.
Joint work with Ankit Garg, Pritish Kamath, and Dmitry Sokolov.
Karchmer and Wigderson introduced an elegant model of computation, called span programs, which capture the complexity of computing with linear algebra over a field F. Monotone span programs are known to be surprisingly powerful and have connections to cryptography; thus, proving lower bounds on the size of monotone span programs is an interesting and difficult task.
In this talk, we discuss some recent work in which we prove a "lifting theorem" from the Nullstellensatz degree of an unsatisfiable CNF (which is a proof complexity measure) to the monotone span program size of a related monotone function over any field F. This characterization of monotone span program size via Nullstellensatz degree leads to the resolution of a number of open problems in monotone complexity theory.
This work is joint with Toniann Pitassi.
In the setting of max-CSPs (like MAX-3-SAT and MAX-CUT), it is now well-understood that the integrality gap of Sherali-Adams relaxations is characterized by the "conic junta degree" of associated non-negative polynomials over the discrete cube. Similarly, the integrality gap of arbitrary linear programs with a given number of constraints can be characterized by the non-negative rank of certain matrices.
Jointly with Chan, Raghavendra, and Steurer (2013), it was shown that strong lower bounds for conic junta degree automatically "lift" to superpolynomial lower bounds on non-negative rank. In a remarkable recent work, Kothari, Meka, and Raghavendra (STOC 2017) established that one can obtain (stretched) exponential lower bounds. This shows, for instance, that no family of linear programs with a subexponential number of inequalities can achieve better than a 1/2-approximation to MAX-CUT.
Their argument is quite technical, but by taking inspiration from the recent work of Goos, Pitassi, and Watson (FOCS 2017) on lifting theorems for BPP, one can simplify it substantially. I will present a sketch of this simplification that arises from (ongoing) work with Raghu Meka and Thomas Vidick.
In the set disjointness problem, the goal is for k parties to determine whether k given subsets of {1,2,3,...,n} have empty intersection. We study the set disjointness problem in the most powerful bounded-error model: the number-on-the-forehead model with k parties and arbitrary classical or quantum communication. I will survey the recent progress on this problem and present the strongest lower bound to date, Omega(sqrt{n}/2^{k}*k), which is tight for quantum protocols and tight up to a square for classical protocols (Sherstov, J. ACM 2014).
The proof revolves around the notion of a directional derivative of a multiparty protocol, and is a form of lifting of approximate degree to communication complexity. No knowledge of quantum computing will be necessary.