CSS.324.1 Analysis of Boolean Functions



  • 2020 Autumn/Monsoon (Sept - Jan)


- Introduction to the Fourier representation for Boolean functions
- Application to linearity testing, and Hastad's 3-bit PCP
- Voting theory and Arrow's theorem
- Learning algorithms from spectral concentration
- Goldreich-Levin theorem from the Fourier perspective
- Hardness amplification
- Hypercontractivity, FKN Theorem, and the KKL Theorem
- Fourier analysis on the biased hypercube and applications
- Invariance principles and the Berry-Essen theorem
- Roth's theorem on 3-term APs over integers