  The $\epsilon$-approximate degree of a function $f\colon X \to \{0, 1\}$ is
the least degree of a multivariate real polynomial $p$ such that $|p(x)-f(x)|
\leq \epsilon$ for all $x \in X$. We determine the $\epsilon$-approximate
degree of the element distinctness function, the surjectivity function, and the
permutation testing problem, showing they are $\Theta(n^{2/3}
\log^{1/3}(1/\epsilon))$, $\tilde\Theta(n^{3/4} \log^{1/4}(1/\epsilon))$, and
$\Theta(n^{1/3} \log^{2/3}(1/\epsilon))$, respectively. Previously, these
bounds were known only for constant $\epsilon.$
  We also derive a connection between vanishing-error approximate degree and
quantum Merlin--Arthur (QMA) query complexity. We use this connection to show
that the QMA complexity of permutation testing is $\Omega(n^{1/4})$. This
improves on the previous best lower bound of $\Omega(n^{1/6})$ due to Aaronson
(Quantum Information & Computation, 2012), and comes somewhat close to matching
a known upper bound of $O(n^{1/3})$.
