Theory of Computing
-------------------
Title     : Dual Polynomials for Collision and Element Distinctness
Authors   : Mark Bun and Justin Thaler
Volume    : 12
Number    : 16
Pages     : 1-34
URL       : https://theoryofcomputing.org/articles/v012a016

Abstract
--------

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
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.