- STOC '06: Gowers Uniformity, Influence of Variables, and PCPs by Alex Samorodnitsky and Luca Trevisan. Topic: Hardness of Approximation and pure Fourier Analysis.
- FOCS 2005: Nonembeddability theorems via Fourier analysis by Subhash Khot and Assaf Naor. Topic: Metric Spaces.
- GAFA journal 2007: Boolean functions with small spectral norm by Ben Green and Tom Sanders. Topic: Classical Analysis. (Mentioned in class today.)
- COLT 2006: Improved lower bounds for learning intersections of halfspaces by Adam Klivans and Sasha Sherstov. Topic: Learning Theory.
- FOCS 2005: On non-approximability for quadratic programs by Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, and Muli Safra. Topic: Hardness of Approximation.
- FOCS 2005: On Delsarte's Linear Programming Bounds for Binary Codes by Michael Navon and Alex Samorodnitsky. Topic: Coding Theory.
- FOCS 2005: Lower bounds for the noisy broadcast problem by Navin Goyal, Guy Kindler, and Mike Saks. Topic: Distributed Networks.
- Complexity 2005: On the hardness of approximating Multicut and Sparsest-Cut by Shuchi Chawla (of CMU), Robi Krauthgamer, Ravi Kumar, Yuval Rabani, and D. Sivakumar. Topic: Hardness of Approximation.
- Improving on a Complexity 2005 paper: Learning symmetric k-juntas in time $n^{o(k)}$ by Mihail Kolountzakis, Evangelos Markakis, and Aranyak Mehta. Topic: Number Theory and Learning Theory.

The first few papers in the list may be particularly readable for people taking the class.

## No comments:

Post a Comment