Dual Polynomials for Collision and Element Distinctness

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

25 pages

References in corpus (9)

• Negative weights make adversaries stronger
• Quantum Search on Bounded-Error Inputs
• Quantum lower bounds for the collision and the element distinctness problems
• Communication Lower Bounds Using Dual Polynomials
• A Dual Polynomial for OR
• Faster Algorithms for Privately Releasing Marginals
• Distribution-Independent Reliable Learning
• Adversary Lower Bound for the k-sum Problem
• Faster Private Release of Marginals on Small Databases

Cited by in corpus (1)

• Adaptivity vs Postselection