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)


Tentative plan: