Lectures

LectDateTopicReference
Linear Programming
1 01/08/15 Introduction
Turing Machine
2 01/13/15 TM basics, recursive and re languages [P2,S3]
3 01/15/15 Variants of TM, Linear speed up [P2,S3]
4 01/20/15 Universal TM [P2,S3]
Decidability
5 01/22/15 Halting problem [P3,S4]
6 01/27/15 Reducibility, undecidability [P3,S5]
Complexity Classes
7 01/29/15 Complexity measures, complexity classes [P7,S7]
8 02/03/15 Hierarchy theorems [P7,S9]
9 02/05/15 Finite automaton, regular languages [S1]
10 02/10/15 Reductions & complete problems [P8,S7]
NP
11 02/12/15 NPC & Cook-Levin Theorem [P9,S7,AB2]
02/17/15 Class Cancelled
12 02/19/15 Web of NPC problems, co-NP [P9-10,AB2]
02/24/15 Midterm
02/26/15 Class Cancelled
Beyond NP
13 03/03/15 Space complexity, Savitch's theorem, PSPACE [AB4,P7,S8]
14 03/05/15 Alternating TM [AB5,P16,S10]
15 03/17/15 Oracle TM, Polynomial hierarchy [P17,AB5]
16 03/19/15 #P, Beyond PSPACE
Randomized Computation
17 03/24/15 Randomized TM, complexity classes [P11,AB7]
18 03/26/15 Polynomial identity, BPP [P11,AB7]
Boolean Circuits
19 03/31/15 Cicruit lower bounds, NC, and P-Completeness [AB6,S10]
Interactive Proofs & Cryptography
20 04/02/15 Interactive proof systems, program checking [AB8]
21 04/07/15 IP=PSPACE [AB8]
22 04/09/15 Perfect secrecy, one way functions [AB9]
23 04/14/15 Zero knowledge [AB9]
PCP
24 04/16/15 PCP Theorem [AB11]
25 04/21/15 Hardness of approximability [AB11]
04/27/15 Final Exam (2:00-5:00pm)

page top