COMP 760 (Winter 2014): Harmonic Analysis of Boolean Functions
- Instructor's contact: See my homepage.
- Time and Location: Tuesdays 3:00-4:30 at McConnell 103, and Thursdays 11:30-13:00 at McConnell 320
What is it about? This course is intended for graduate students in theoretical computer science or mathematics. Its purpose is to study Boolean functions via tools from Fourier analysis and functional analysis. This analytic approach plays an essential role in modern theoretical computer science and combinatorics (e.g. in circuit complexity, hardness of approximation, machine learning, communication complexity, graph theory), and it is the key to understanding many fundamental concepts such as pseudo-randomness. For more on the importance and impact of this area, I encourage you to read Guest Editors' Foreword on the special issue of Theory of Computing on this topic.
Will we discuss open problems? There will be plenty of open problems, and (hopefully) in different levels of difficultly. I hope that by the end of the semester we can make progress on some of these problems. There is already a list of open problems compiled by Ryan O'Donnell for the Simons Symposium.
What are the prerequisites? No background in harmonic analysis is required. The main prerequisite is mathematical maturity and interest in some of the application fields (theoretical computer science, combinatorics, discrete probability, Fourier analysis, functional analysis).
Evaluation? It will be based on assignments and a final presentation.
Lecture notes (I will keep updating this file and add the notes for the new lectures)
- First lecture: Chapter 1 (Basic Functional Analysis).
- Lectures 2-3: Chapter 2 (Fourier analysis of Finite Abelian Groups).
- Lecture 4: Chapter 3 (Property Testing).
- Lecture 5: Chapter 4 (Circuit complexity).
Tentative plan:
- Week 1: Introduction to the course, Fourier Analysis of Finite Abelian Groups.
- Week 2: Fourier Uniformity and Linearity Test. Learning low degree polynomials and decision trees.
- Week 3: Fourier spectrum of functions with bounded depth circuits: Hastad's Switching lemma and [Linial, Mansour, Nisan], [Boppana, The Average Sensitivity of Bounded Depth Circuits] and [Razborov-Smolensky].
- Week 4 : Random Walks on the cube, Contractivity, Hypercontractivity, Semi-group method
- Week 5: Friedgut's junta theorem, KKL inequality, Chang's lemma.
- Week 6-7: Stroock-Varopoulos inequality, Logarithmic Sobolev inequality, Expansion: Poincare inequality, Spectral gap, Reverse Bonami-Beckner.
- Week 8: Gaussian spaces, Gaussian surface area and intersection of half spaces [Kane], [Nazarov], [Ball].
- Week 9: Berry-Esseen Theorem, Invariance Principle, Majority is stablest.
- Week 10: Applications of majority is stablest.
- Week 11-13: TBA.