The Approximate Degree of Surjectivity: How the Sausage is Made

Approximate degree is a basic measure of the complexity of boolean functions which has found applications to lower bounds in quantum query complexity, communication complexity, circuit complexity, and relativized complexity. I will describe in as much detail as possible the proof of a tight ~Omega(n^{3/4}) lower bound on the approximate degree of the Surjectivity function.

The lower bound for Surjectivity is, in fact, a special case of a more general hardness amplification theorem which yields approximate degree lower bounds for a broad class of (non-block-)composed functions.

This talk is intended to complement the high-level overview given in the Boolean Devices workshop, but will be entirely self-contained.

It is based on joint works with Robin Kothari and Justin Thaler.