Lect. | Date | Topics | Handouts | Reading |
---|---|---|---|---|
1 | Jan. 13 |
Introduction, Turing Machines, Non-Determinism, Church Turing Hypothesis |
[HMU, Ch 8] | |
2 | Jan. 18 | P, NP, NP-Completeness Cook-Lewin Theorem and 3SAT |
[Pap, Ch9] [HMU, Ch10] |
|
3 | Jan. 20, 27 |
NP-Completeness via Reductions coNP, EXPTIME, NEXPTIME |
[GJ, Ch3,4] [Pap, Ch9] [HMU, Ch10] |
|
Jan. 25 | No Class
- SODA 2005 |
|||
5 |
Feb. 1,3 |
Space Complexity PSPACE Completeness and TQBF Examples of PSPACE Complete Problems |
HW1 |
[Pap, Ch19] [HMU, Ch11] |
7 |
Feb. 8 |
L, NL, Logspace Reductions PATH is NL-Complete |
[Pap, Ch7,16] |
|
8 |
Feb. 10 |
PSPACE=NPSPACE [Savitch 1970] NSPACE=coNSPACE |
[Pap, Ch7] |
|
9 |
Feb. 15 |
Diagonalization Time-Space Hierarchy Theorems |
[Pap, Ch7,8] |
|
10 |
Feb. 17 |
Relativized Proof Techniques Oracle Turing Machines P versus NP via Diagonalization? |
[Pap, Ch14] | |
11 | Feb. 22 |
Polynomial Hierarchy (PH) Properties of PH Oracle Characterization of PH |
HW2 | [Pap, Sec16.2] [CKS] |
12 | Feb. 24 |
Circuit Complexity, P/poly, Logspace uniform classes |
[Pap, Ch11] | |
13 |
Mar. 1 |
Can P/poly resolve P versus NP? Parallel Computation |
[Pap, Ch11] |
|
14 |
Mar. 3 |
Log-depth Circuits, NC Relation of NC to Parallel Computing P-Completeness and Linear Programming |
[Pap, Ch11] |
|
15 |
Mar. 8 |
Randomized Complexity: RP, BPP,
ZPP Examples of PTMs |
[Pap, Ch11] [HMU, Ch11] |
|
16 |
Mar. 10 | Mid-Term Exam | ||
Mar. 15,17 | No Class - SPRING BREAK | |||
17 |
Mar. 22 |
Proof of the Schwartz-Zippel
Lemma Relation of BPP to PH and P/poly |
||
18 |
Mar. 24 |
Trapdoor Functions, Cryptography RSA and Discrete Log Cryptosystems |
|
[Pap, Ch18] |
19 |
Mar. 29 |
One Way Functions: Discrete Log Pseudorandomness: Two equivalent definitions |
[Pap, Ch11] |
|
20 |
Mar. 31 |
Goldreich-Levin Hardcore Bit,
and Pseudorandom Number Generators |
||
Apr. 5,7 |
No
Class - ICDE 2005 |
|||
21
|
Apr. 12 |
Interactive Proofs (IP) Zero Knowledge Proofs Public Randomness and the class AM |
HW3 HW4 |
[Pap, Ch19] |
22 |
Apr. 14 |
IP = PSPACE |
[Pap, Ch19] |
|
23 |
Apr. 19 |
IP = PSPACE (contd.) Program Checking Multiprover Interactive Proofs (MIP) |
[Pap, Ch19] |
|
24 |
Apr. 21 |
Relation between MIP and Proof
Verification History of the PCP Theorems Hardness of Approximating MAX-SAT |
||
25 |
Apr. 26, 28 |
NP in PCP(poly(n),1) |
||
27 |
Apr. 28-29 |
End-Term
Exam (Take Home) |