A Nearly Optimal Lower Bound on the Approximate Degree of AC${}^0$

Mark Bun, Justin Thaler

The approximate degree of a Boolean function $f:\{-1,1{\}}^n\to \{-1,1\}$ is the least degree of a real polynomial that approximates $f$ pointwise to error at most…