Course Information
Instructor: Swastik Kopparty
(swastik.kopparty@utoronto.ca)
Lectures: Tuesdays, 1:00–3:00 p.m., GB 120
Office hours: TBD, SF 3324
Email me if you are not registered for the course and are interested in getting on the mailing list.
Course Description
This course will study Boolean functions; namely functions from {0,1}^n to {0,1}. Topics include: CNF and DNF representations, decision trees, approximate and exact representations by polynomials over reals and finite fields, Fourier expansions, influence of variables, approximate juntas, formula and circuit complexity, constant-depth circuit complexity and pseudorandomness. We will see applications to learning theory, error-correcting codes, social choice and cryptography.
Prerequisites
Undergraduate-level linear algebra, probability, combinatorics. Mathematical maturity.
Assessment
- Homework: 30%
- Scribing: 40%
- Project and presentation: 30%
References
- Ryan O'Donnell, Analysis of Boolean Functions
- Stasys Jukna, Boolean Circuit Complexity
- Stasys Jukna, Extremal Combinatorics
- Michael Luby and Avi Wigderson, Pairwise Independence and Derandomization
Lecture Schedule
- September 8: TBD
- September 15: TBD
- September 22: TBD
- September 29: TBD
- October 6: TBD
- October 13: TBD
- October 20: TBD
- October 27: No class — Fall Reading Week
- November 3: TBD
- November 10: TBD
- November 17: TBD
- November 24: TBD
- December 1: TBD