Computer Science/Discrete Mathematics Seminar II
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,1}^n \to {0,1}$, we show there is a constant size gadget g: $X \times Y \to {0,1}$, such that $f \circ 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."