** Abstract: **

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. The approximate degree of f is known to be a lower bound on the quantum query complexity of f (Beals et al., FOCS 1998 and J. ACM 2001).

We resolve or nearly resolve the approximate degree and quantum query complexities of several basic functions. Specifically, we show the following:

- k-distinctness: For any constant k, the approximate degree and quantum query complexity of the k-distinctness function is \Omega(n^{3/4-1/(2k)}). This is nearly tight for large $k$, as Belovs (FOCS 2012) has shown that for any constant k, the approximate degree and quantum query complexity of k-distinctness is O(n^{3/4-1/(2^{k+2}-4)}).
- Image Size Testing: The approximate degree and quantum query complexity of testing the
size of the image of a function [n]-->[n] is \tilde{\Omega}(n^{1/2}). This proves a conjecture of
Ambainis et al. (SODA 2016), and it implies tight lower bounds on the approximate degree and quantum query
complexity of the following natural problems.
- k-junta testing: A tight \tilde{\Omega}(k^{1/2}) lower bound for k-junta testing, answering the main open question of Ambainis et al. (SODA 2016).
- Statistical Distance from Uniform: A tight \tilde{\Omega}(n^{1/2}) lower bound for approximating the statistical distance from uniform of a distribution, 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 for approximating Shannon entropy up to a certain additive constant, answering a question of Li and Wu (2017).

- 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, Quantum Inf. Comput. 2012 and Sherstov, FOCS 2015).

** Versions: **

- Manuscript [arXiv] [slides giving unified
overview of BT17 and BKT18 (size: 3MB)]
[slides more focused on BKT18 (size: 11MB)]

- These lecture notes elucidate various aspects of the proof. Whereas the proof in the paper takes place entirely in the "dual" world, the notes explain how to replace a key step of the proof with a "primal" argument that many will find more intuitive.