Note: This list is a work in progress and will be adjusted before and throughout the semester. The ordering of the papers does not (yet) reflect the ordering of topics in the course.

1. H. Buhrmann, R. de Wolf, Complexity Measures and Decision Tree
2. L. Lovasz, N. E. Young, Lecture notes on Evasiveness of Graph Properties
3. P. Hatami, R. Kulkarni and D. Pankratov, Variations on the Sensitivity Conjecture
4. R. de Wolf, A brief introduction to fourier analysis on the boolean cube, Theory of Computing (ToC Library, Graduate Surveys), 6, 2008.
5. E. Friedgut and G. Kalai, Every monotone graph property has a sharp threshold, Proc. Amer. Math. Soc. 124 (1996) 2993-3002.
6. E. Friedgut, Influences in Product Spaces, KKL and BKKKL revisited, Combinatorics, Probability and Computing 13 (2004) 17--29
7. E. Friedgut, Sharp Thresholds of Graph Properties and the k-sat problem , J. Amer. Math. Soc. 12 (1999) 1017-1054.
8. E. Friedgut, Boolean Functions with Low Average Sensitivity Depend on Few coordinates. Combinatorica Vol 18 (1) 1998 pp. 27-36.
9. E. Friedgut, G. Kalai and A. Naor, Boolean Functions whose fourier transform is concentrated on the first two levels",Adv. in Appl. Math., 29(2002), 427-437.
10. E. Friedgut, J. Kahn, and A. Wigderson, Computing Graph Properties by Randomized Subcube Partitions Randomization and Approximation Techniques in Computer Science, 6th International Workshop, RANDOM 2002, pp. 105-113, 2002 .
11. J. Bourgain, On the distribution of the fourier spectrum of boolean functions
12. D. Rubinstein, Sensitivity vs. Block Sensitivity of boolean functions Combinatorica 15 (2) (1995) 297--299.
13. Eric Blais, Testing Juntas Nearly Optimally , Proc. ACM STOC 2009, 151--158.
14. J. Kahn and G. Kalai, Thresholds and expectation thresholds , Combinatorics Probability and Computing 16, May 2007.
15. G. Kalai, J. Kahn, N. Linial, The influence of variables on boolean functions 29th Symposium on the Foundations of Computer Science, White Planes, 1988, 68-80.
16. I. Diakonikolas and R. Servedio and L.-Y. Tan and A. Wan, http://www.cs.columbia.edu/~rocco/papers/ccc10.html >A regularity lemma, and low-weight approximators, for low-degree polynomial threshold functions 25th IEEE conference on Computational Complexity, 2010.
17. Diakonikolas and P. Harsha and A. Klivans and R. Meka and P. Raghavendra and R. Servedio and L.-Y. Tan, Bounding the average sensitivity and noise sensitivity of polynomial threshold functions , 42nd Annual Symposium on Theory of Computing (STOC), 2010.
18. K. Matulef and R. Rubinfeld and R. O'Donnell and R. Servedio Testing Halfspaces SIAM Journal on Computing, 39(5), 2010.
19. R. O'Donnell, J. Wright, and Y. Zhou, The fourier entropy-influence conjecture for certain classes of boolean functions Proceedings ICALP 2011
20. R. O'Donnell, Y. Wu and Y. Zhou, Optimal lower bounds for locality sensitive hashing (except when q is tiny)
21. R. O'Donnell and R. Servedio, The Chow parameters problem
22. E. Mossel, R. O'Donnell,K. Oleszkiewicz, Noise stability of functions with low influences: invariance and optimality , Annals of Mathematics 171(1), pp. 295-341 (2010).
23. R. O'Donnell, M. Saks, O. Schramm, and R. Servedio, Every decision tree has an influential variable Proc. IEEE Symp. on Foundations of Computer Science 2005.