pdf icon
Volume 12 (2016) Article 16 pp. 1-34
Dual Polynomials for Collision and Element Distinctness
Received: August 17, 2015
Revised: May 8, 2016
Published: October 13, 2016
Download article from ToC site:
[PDF (404K)] [PS (2147K)] [Source ZIP]
Keywords: polynomials, polynomial approximation, approximate degree, quantum computing, collision problem, element distinctness
ACM Classification: F.1.2, F.1.3
AMS Classification: 68Q12, 68Q17

Abstract: [Plain Text Version]

$ \newcommand{\collision}{\textsf{Collision}} \newcommand{\elementdistinctness}{\textsf{Element Distinctness}} $

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.