Revised: May 8, 2016

Published: October 13, 2016

**Keywords:**polynomials, polynomial approximation, approximate degree, quantum computing, collision problem, element distinctness

**Categories:**complexity theory, polynomials - multivariate, polynomial approximation, approximate degree, quantum computing, collision, element distinctness

**ACM Classification:**F.1.2, F.1.3

**AMS Classification:**68Q12, 68Q17

**Abstract:**
[Plain Text Version]

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 $\widetilde{\Omega}(n^{1/3})$ and
$\widetilde{\Omega}(n^{2/3})$ lower bounds on the approximate degree of the
$\collision$ and $\elementdistinctness$ 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 $\elementdistinctness$ functions. Our
constructions are heavily inspired by Kutin's
(*Theory of
Computing*, 2005)
refinement and simplification of Aaronson and Shi's results.