Oracles and the Polynomial Hierarchy
- Papadimitriou [1]: Section 14.3 pp.339-343, Section 17.2, pp.424-429 (χωρίς την απόδειξη του θ. 17.12)
- Διαφάνειες: 158-205

Structure of NP
- Papadimitriou [1]: Sections 14.1, 14.2 (χωρίς τις αποδείξεις των θ. 14.2, 14.3)
- Arora-Barak [2]: Theorem 2.22 (Ch.2, p.57), Chapter 3 (Η απόδειξη του θ. Ladner είναι διαφορετική εδώ, μέσω padding!)
- Διαφάνειες: 207-261 (δλδ χωρίς την απόδειξη του θεωρήματος Mahaney)

Randomized Computation
- Arora-Barak [2]: Sections 7.1, 7.3, 7.4, 7.5 (όχι την απόδειξη του θ. 7.15 [Sipser-Gacs])
- Διαφάνειες: 277-328

Non-Uniform Complexity and Circuit Lower Bounds
- Arora-Barak [2]: Sections 6.1 - 6.7, 14.1, 14.2, 14.4, 23.1, 23.2
- Διαφάνειες: 330-433

Interactive Proofs
- Arora-Barak [2]: Sections 8.1, 8.2 (όχι τα 8.2.2, 8.2.3), 8.3 (όχι τα 8.3.2, 8.3.3), 8.4, 8.5
- Διαφάνειες: 437-475 (όχι την απόδειξη του θ. Shamir)

Pseudorandomness and Derandomization
- Arora-Barak [2]: Sections 20.1, 20.3, 20.4 (χωρίς τις αποδείξεις)
- Διαφάνειες: 504-559 (χωρίς την τελική απόδειξη του Easy Witness Lemma, αλλά με τις αποδείξεις των αρικών λημμάτων)

Η αρίθμηση των διαφανειών αναφέρεται στον αριθμό σελίδας του .pdf: https://courses.corelab.ntua.gr/pluginfile.php/10246/mod_folder/content/0/CC_Slides_2023_01_16.pdf?forcedownload=1

Η εξέταση θα γίνει με κλειστά βιβλία!