  The approximate degree of a Boolean function f is the least degree of a real
polynomial that approximates f pointwise to error at most 1/3. Approximate
degree is known to be a lower bound on quantum query complexity. We resolve or
nearly resolve the approximate degree and quantum query complexities of the
following basic functions:
  $\bullet$ $k$-distinctness: For any constant $k$, the approximate degree and
quantum query complexity of $k$-distinctness is $\Omega(n^{3/4-1/(2k)})$. This
is nearly tight for large $k$ (Belovs, FOCS 2012).
  $\bullet$ Image size testing: The approximate degree and quantum query
complexity of testing the size of the image of a function $[n] \to [n]$ is
$\tilde{\Omega}(n^{1/2})$. This proves a conjecture of Ambainis et al. (SODA
2016), and it implies the following lower bounds:
  $-$ $k$-junta testing: A tight $\tilde{\Omega}(k^{1/2})$ lower bound,
answering the main open question of Ambainis et al. (SODA 2016).
  $-$ Statistical Distance from Uniform: A tight $\tilde{\Omega}(n^{1/2})$
lower bound, answering the main question left open by Bravyi et al. (STACS 2010
and IEEE Trans. Inf. Theory 2011).
  $-$ Shannon entropy: A tight $\tilde{\Omega}(n^{1/2})$ lower bound, answering
a question of Li and Wu (2017).
  $\bullet$ Surjectivity: The approximate degree of the Surjectivity function
is $\tilde{\Omega}(n^{3/4})$. The best prior lower bound was $\Omega(n^{2/3})$.
Our result matches an upper bound of $\tilde{O}(n^{3/4})$ due to Sherstov,
which we reprove using different techniques. The quantum query complexity of
this function is known to be $\Theta(n)$ (Beame and Machmouchi, QIC 2012 and
Sherstov, FOCS 2015).
  Our upper bound for Surjectivity introduces new techniques for approximating
Boolean functions by low-degree polynomials. Our lower bounds are proved by
significantly refining techniques recently introduced by Bun and Thaler (FOCS
2017).
