CSC 2429, MAT 1304: Circuit Complexity
Fall 2016
Lectures: Tuesdays 3-5, Sidney Smith Hall 2101
Instructor: Benjamin Rossman
Office hours: by appointment (in Sandford Fleming 2302B or Bahen 6214)
Recommended text: Stasys Jukna "Boolean Function Complexity". Available to UofT students
here (follow either link to Scholars Portal Books or SpringerLINK eBooks)
Lecture notes from other courses: Allender, Buss, Kopparty, Zwick
LECTURE NOTES
- Lecture 1, Sep 13
Overview, Counting Arguments, Formula Balancing
- Lecture 2, Sep 20
Gate Elimination, Formula Lower Bounds
- Lecture 3, Sep 27
AC^{0} Circuits, Switching Lemma
- Lecture 4, Oct 4
Proof of Switching Lemma, AC^{0}[p]
- Lecture 5, Oct 11
Average-Case Lower Bounds, Derandomization, Monotone Complexity
- Lecture 6, Oct 18
(guest lecture: Robert Robere)
Exponential Lower Bounds for Monotone Computation
(see the paper here)
- Lecture 7, Oct 25
The Subgraph Isomorphism Problem
- Lecture 8, Nov 1
AC^{0} Circuit Size of SUB(G)
- Lecture 9, Nov 15
AC^{0} Circuit Size of SUB(G), Continued
- Handout on relations (projection, restriction, join, density)
- Lecture 10, Nov 22
Pathsets
- Lecture 11, Nov 29
Pathset Complexity
- Lecture 12, Dec 6
Pathset Complexity, Continued