Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Dual Polynomials for Collision and 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 $\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.

32
The categories of this paper are: atom-ph
7
The categories of this paper are: hep-th
11
The categories of this paper are: hep-lat
14
The categories of this paper are: math-ph
33
The categories of this paper are: plasm-ph
12
The categories of this paper are: nucl-th
29
The categories of this paper are: funct-an
37
The categories of this paper are: supr-con
9
The categories of this paper are: nlin
15
The categories of this paper are: nucl-ex
5
The categories of this paper are: gr-qc
4
The categories of this paper are: cond-mat
30
The categories of this paper are: q-alg
18
The categories of this paper are: econ
2
The categories of this paper are: math
16
The categories of this paper are: stat