1. Forrelation: A Problem that Optimally Separates Quantum from Classical Computing. S. Aaronson, A. Ambainis.

  2. Quantum Lower Bounds by Polynomials. R. Beals, H. Buhrman, R. Cleve, M. Mosca.

  3. Polynomials, Quantum Query Complexity, and Grothendieck’s inequality. S. Aaronson, A. Ambinis, J. Iraids, M. Kokainis.

  4. Complexity measures and decision tree complexity: a survey. H. Buhrman, R. De Wolf.
    - the proof of D(f) \leq 2 deg(f)^3 can be found here.
    - this table from this paper provides the most up to date known relationships among (in the "zoo") different complexity measures.

  5. The proof of sensitivity(f) \geq \sqrt{deg(f)}, H. Huang, see here.
    - For a different exposition see     here.

  6. The Need for Structure in Quantum Speedups. S. Aaronson, A. Ambainis.

  7. On the Fourier tails of bounded functions over the discrete cube. I. Dinur, E. Friedgut, G. Kindler, R. O’Donnell.

  8. Every decision tree has an influential variable. R. O’Donnell, M. Saks, O. Schramm, R. Servedio.
    - for a martingale proof see here.

  9. a) Quantum Mechanics helps in searching for a needle in a haystack. L. Grover.
    b) Deutsch–Jozsa algorithm. See S. Aaronson's lecture notes
    - as you see there are two topics. They both are very short, and that is the reason we decided to include them together. These are two important algorithms illustrating that to get exponential speedups via quantum algorithms certain structures are needed. Perhaps a big problem is to understand in general what structures are needed for exponential speedups.

  10. M. Talagrand “On russo’s approximate zero-one law”.
    - Talagrand's paper proves an inequality which implies two things: the famous Kahn-Kalai-Linial (KKL) inequality "The influence of variables on Boolean functions. J. Kahn, G. Kalai, N. Linial", and sharp threshold phenomena for monotone graphs with large connectivity. An easier proof of Talagrand's inequality with uniform measure on the hamming cube can be found in "D. Cordero-Erausquin and M. Ledoux. Hypercontractive measures, Talagrand’s inequality, and influences".

  11. On the Fourier Spectrum of Functions on Boolean Cubes. A. Defat, M. Mastylo, A. Perez.

  12. On the degree of Boolean functions as real polynomials. N. Nisan, M. Szegedy.

  13. On the distribution of the Fourier spectrum of Boolean functions. J. Bourgain.

  14. Noise Stability of Weighted Majority, Y. Peres. https://arxiv.org/abs/math/0412377