CSE 291 - Fourier analysis of boolean functions (Winter 2017)
Time: Mondays & Wednesdays 5:00-6:20pm
Room: CSE (EBU3B) 4258
Instructor: Shachar Lovett, email: firstname.lastname@example.org
Fourier analysis is a powerful tool used to study boolean functions. It has
many applications in computer science, for example in learning theory, social choice theory, cryptography, complexity theory and more.
This class will cover the necessary mathematical background, as well as explore many applications.
We will follow the book Analysis of Boolean functions
by Ryan O'Donnell. It can be downloaded for free from the website, or purchased on Amazon.
Homework and a take-home exam.
Please submit homework in latex (as a pdf). You may work individually or in pairs.
Concise summaries of Ryan's book, mostly for myself, but you are free to use them
- Chapter 1: The basics [pdf]
- Chapter 2: Social choice theory [pdf]
- Chapter 3: Spectral structure and learning [pdf]
- Chapter 4: DNFs and small depth circuits [pdf]
- Chapter 6: Pseudorandomness [pdf]
- Chapter 9: The hypercontractive theorem and its applications [pdf]