  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_\infty$ norm. In an influential result, Aaronson and
Shi (J. ACM 2004) proved tight $\tilde{\Omega}(n^{1/3})$ and
$\tilde{\Omega}(n^{2/3})$ lower bounds on the approximate degree of the
Collision and Element Distinctness functions, respectively. Their proof was
non-constructive, using a sophisticated symmetrization argument and tools from
approximation theory.
  More recently, several open problems in the study of approximate degree have
been resolved via the construction of dual polynomials. These are explicit dual
solutions to an appropriate linear program that captures the approximate degree
of any function. We reprove Aaronson and Shi's results by constructing explicit
dual polynomials for the Collision and Element Distinctness functions.
