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 + oral presentation of HW: 20%
- Attendance and Participation: 30%
- Scribing: 30%
- 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
Scribing Info
guidelines, latex definitions file, sample notesHomework
Papers for Projects
- List of papers for projects. Please form groups of size 1 or 2, and claim papers on this list (on the course piazza). Your project will involve: reading the paper, producing a 5-10 page writeup which includes an overview of the whole paper and a detailed proof of one important or interesting mathematical fact from the paper, and giving a 10 minute presentation to the class.
Lecture Schedule
- September 8: Circuits, Shannon's theorem
- September 15: Formulas, Nechiporuk's lower bound
- September 22: Branching programs, Barrington's theorem
- September 29: No class - makeup will be scheduled near the end of the term
- October 6: Decision tree complexity, certificate complexity, CNFs and DNFs
- October 13: Learning heavy Fourier coefficients
- October 20: Learning decision trees, linearity testing
- October 27: No class — Fall Reading Week
- November 3: Arrow's Impossibility Theorem, random walks on the hypercube
- November 10: Noise operator, Hypercontractivity, Influences
- November 17: TBD
- November 24: TBD
- December 1: TBD