CS 6817: Analysis of Boolean Functions (Fall 2020)
Instructor: Eshan Chattopadhyay
Class schedule: Tuesdays and Thursdays, 9:55-11:10am
Location: Schwartz Ctr Performing Arts, Room 111, map
Attendance: Synchronous attendance is not mandatory, but highly encouraged.
Office hours: Wed 10:30am -11:30 am (see Canvas for zoom link)
Logistics:
Syllabus (includes a tentative list of topics), Piazza (for discussions related to this class), Canvas (Relevant zoom links for lectures and office hours, video of lectures, notes from lectures, and homeworks will be posted here).
About this course: A central focus of this course will be to uncover properties of Boolean functions via analytic methods (such as studying their Fourier spectrum). Such methods have seen remarkable applications in various fields of theoretical computer science such as property testing, hardness of approximation, learning theory, pseudorandomness, etc, and is by now an essential ingredient in a theorist's toolkit. These methods have also found nice applications beyond computer science, in areas such as combinatorics, random graphs and metric spaces. We will develop this theory from the basics and cover a variety of applications in the course.
Prerequisites: CS 4820 or permission from the instructor. In general, some mathematical maturity is expected. Familiarity with basic notions of algebra (such as finite fields, basics of vector spaces, polynomials), linear algebra, discrete probability, and basics of computational complexity theory will come in handy.
Resources
- Textbook: We will follow the book Analysis of Boolean Functions by Ryan O'Donnell. You can buy the book or find a draft of the book here .
- Excellent lecture notes by Hamed Hatami.
- Some open problems to think about during the course!
- See this amazing list of resources compiled by Li-Yang Tan.
- See Canvas for lecture notes.