Schedule and Notes

Date	Topic
March 30	Computational Models, ipad, video
April 1	Turing Machines and Circuits, ipad, video
April 6	Boolean Circuits, ipad, video
April 8	Counting Arguments for Turing Machines, ipad, video
April 13	Hierarchy Theorems, ipad, video
April 15	NP, ipad, video
April 20	NP-complete problems, ipad, video
April 22	The problem with diagonalization and P vs NP, ipad, video
April 27	Space, ipad, video
April 29	NL vs coNL, ipad, video
May 4	TQBF, ipad, video
May 6	Randomized Algorithms, ipad, video
May 11	Randomized Complexity Classes, ipad, video
May 13	Schwartz-Zippel and the Determinant, ipad, video
May 18	Identity Testing and the Permanent, ipad, video
May 20	Lower bounds for Circuits with Bounded Alternations, ipad, video
May 25	Interactive Proofs, ipad, video
May 27	IP=PSPACE, ipad, video
June 1	IP=PSPACE, ipad, video
June 1	Lower bounds from Communication Complexity, ipad, video
June 4	Homework 4 due
June 10	Final due

Schedule and Notes from Autumn 2018

Date	Topic
September 27	Computational Models
October 2	Turing Machines and Boolean Circuits
October 4	Tight Bounds for Circuits and Counting Arguments
October 9	Diagonalization
October 11	Hierarchy Theorems
October 16	Nondeterministic Polynomial Time
October 18	NP-complete problems
October 23	More NP-complete problems
October 25	The problem with using Diagonalization to separate P and NP
October 30	Space
November 1	NL vs coNL
November 8	TQBF
November 13	Randomized Algorithms
November 20	Randomized Complexity Classes
November 27	Schwartz-Zippel and the Determinant
November 29	Permanent and Interactive Proofs
December 5	Course Evaluation
December 6	IP=PSPACE
December 8	Course Summary