The Polynomial Method in Communication Complexity

A powerful technique developed and extended in the past decade in communication complexity is the so-called "lifting theorems."  The idea is to translate the hardness results from "easier" models, e.g., query complexity, polynomial degrees, to the more challenging communication model.

In this talk, I plan to discuss lifting polynomial degrees to communication lower bounds. For any boolean function f:0,1n→0,1, we show there is a constant size gadget g:  X×Y→0,1, such that f∘g has (deterministic, quantum, unbounded-error probabilistic) communication complexity at least the (exact, approximate, and threshold) degree of f. This particular technique was developed by Sherstov, Razborov-Sherstov in a series of works.

Besides proving strong communication lower bounds, the technique has applications in many areas, especially circuits complexity. Hopefully, we will discuss some of the applications."