Algorithmic Polynomials

Alexander A. Sherstov

The approximate degree of a Boolean function $f(x_1,x_2,\dots ,x_n)$ is the minimum degree of a real polynomial that approximates $f$ pointwise within $1/3$. Upper bounds on…