Approximate degree, secret sharing, and concentration phenomena

Andrej Bogdanov, Nikhil S. Mande, Justin Thaler +1

The $\epsilon$-approximate degree $de{g}_{\epsilon }(f)$ of a Boolean function $f$ is the least degree of a real-valued polynomial that approximates $f$ pointwise to error $\epsilon$. The approximate degree…