The -approximate degree of a function f : X 0 1 is the least degree of a multivariate real polynomial p such that p ( x ) − f ( x ) for all x X . We determine the -approximate degree of the element distinctness function, the surjectivity function, and the permutation testing problem, showing they are ( n 2 3 log 1 3 (1 )) , ( n 3 4 log 1 4 (1 )) , and ( n 1 3 log 2 3 (1 )) , respectively. Previously, these bounds were known only for constant

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 ( n 1 4 ) . This improves on the previous best lower bound of ( 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 ) .