| Date | Topic | References |
| Jan 30th | The class P and the class NP. Nondeterministic Turing machines, equivalent definition of NP. NP-hardness. Example NP-complete problem. Statement of NP-completeness of SAT |
Lecture notes (from 2014 offering) Chap 1 of [AB], Sec 2.1, 2.2 and beginning of 2.3 of [AB] |
| Feb 6th |
Proof that SAT is NP-hard. (Check these notes for a proof of NP-completeness of SAT for a RAM model.) Class coNP. NP and coNP are in EXP. Deterministic time hierarchy theorem. |
Chap 2 et 3.1 of [AB] |
| Feb 13th | Space complexity. L, NL, PSPACE. Relation to time classes. TQBF is PSPACE complete. | Chap 4.1 and 4.2 of [AB] |
| Feb 27th |
Space hierarchy theorem. Composition theorem for space.
NSPACE(S) in SPACE(S^2) (Savitch theorem). Class NL, NL-hardness PATH is NL-complete. State NL = coNL. |
Sec 4.2 and 4.3 (space complexity) of [AB] |
| Mar 6th | Oracle Turing machines. Existence of oracles A,B with P^A=NP^A and P^B \neq NP^B. Polynomial hierarchy. If \Sigma_i = \Pi_i then the hierarchy collapses. | Chap 3 and 5 in [AB] |
| Mar 13th | Midterm exam. Definition of polynomial hierarchy with oracles. Start boolean circuits. | Chap 5 of [AB] |
| Mar 20th |
Boolean circuits, P included in P/poly, uniformity condition for circuit family TMs with advice, Karp-Lipton theorem: If NP included in P/poly, then the polynomial hierarchy collapses. |
Chap 6 of [AB] |
| Mar 27th | Randomized computation: BPP, relation to P/poly and polynomial hierarchy. | Chap 7 of [AB] |
| Apr 3rd | Communication complexity. Lower bound using fooling set bound, equality and disjointness. | Chap 13 of [AB] |
| Apr 10rd | Communication complexity. Application to streaming lower bounds. Randomized communication complexity. Discrepency method and application to the inner product function. | Chap 13 of [AB] |