CSC 2429 / MAT 1304: Circuit Complexity
Winter 2019

ANNOUNCEMENTS: Lectures: Thursdays 4-6, Bahen B026

Instructor: Benjamin Rossman

Office hours: by appointment

Textbook: Stasys Jukna "Boolean Function Complexity". Available to UofT students here (follow either link to Scholars Portal Books or SpringerLINK eBooks)

Background: Make sure you are comfortable with basic probability theory as presented in appendix §A.1.

Workload: Students are expected to attend lectures and encouraged to ask questions. Problems will be assigned during lectures; once or twice during the semester, a subset of these problems will make their way onto official problem sets (assigned at least a week in advance). Volunteers will be sought to scribe lectures on material outside the textbook.

Lecture notes from other courses: Allender, Buss, Kopparty, Servedio, Williams, Zwick

HOMEWORK PROBLEMS (updated March 6). You are asked to submit solutions to your choice of six problems on this list by the end of the term.

Lecture notes

Preliminary outline of topics