Lect | Date | Topic | Reference |
| | 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) |
|