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."



Member, School of Mathematics