Class material

Num. Topic Reference Date
1 Introduction, Turing machinesComplexity Theory (Arora-Barak) chap. 11/11/16
2 The classes P and NPCT chap. 1.6, 2.12/11/16
3 NP completeness and reductionsCT chap. 2.28/11/16
4 More NP-complete languagesCT chap. 2.49/11/16
5 Cook-Levin theoremCT chap. 2.315/11/16
6 Self reducibility, co-NPCT chap. 2.5, 2.616/11/16
7 Approximation algorithms, vertex cover, set coverSee these notes22/11/16
8 Hardness of approximationSection 1 in these notes (they also contain the equivalence of the classical PCP theorem to the one shown in class)‎23/11/16
9 Diagonalization, Deterministic Time Hierarchy TheoremCT chap. 3.129/11/16
10 Non-Deterministic Time Hierarchy, Space bounded computationnotes, CT chap. 4.130/11/16
11 Space: Determinism vs. Non-Deterministic (Savitch's Theorem). The class NL CT chap. 4.2.16/12/16
12 NSPACE closed Space under complement CT chap. 4.3.27/12/16
13 Log-space reductions, NL completness, 2SAT in NLCT chap. 4.313/12/16
14 PSPACE completenessCT chap. 4.214/12/16
15 Randomized algorithms: min-cut. The class RPProbability and Computation (Mitzenmacher & Upfal) chap. 1.4, CT chap. 7.1,7.3, 20/12/16
16 Randomized complexity classes: RP and BPPCT chap. 7.1,7.3,7.421/12/16
17 Interactive Proofs. Graph Non Isomorphism in IP.CT chap. 8.128/12/16
18 coNP in IP.CT chap. 8.33/1/17