Dual Polynomials for Collision and Element Distinctness

Mark Bun, Justin Thaler

The approximate degree of a Boolean function $f:\{-1,1{\}}^n\to \{-1,1\}$ is the minimum degree of a real polynomial that approximates $f$ to within error $1/3$ in the $\ell_\inf…