Lect.  Date  Topics  Handouts  Reading 

1  Jan. 13 
Introduction, Turing Machines, NonDeterminism, Church Turing Hypothesis 
[HMU, Ch 8]  
2  Jan. 18  P, NP, NPCompleteness CookLewin Theorem and 3SAT 
[Pap, Ch9] [HMU, Ch10] 

3  Jan. 20, 27 
NPCompleteness 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 NLComplete 
[Pap, Ch7,16] 

8 
Feb. 10 
PSPACE=NPSPACE [Savitch 1970] NSPACE=coNSPACE 
[Pap, Ch7] 

9 
Feb. 15 
Diagonalization TimeSpace 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 
Logdepth Circuits, NC Relation of NC to Parallel Computing PCompleteness and Linear Programming 
[Pap, Ch11] 

15 
Mar. 8 
Randomized Complexity: RP, BPP,
ZPP Examples of PTMs 
[Pap, Ch11] [HMU, Ch11] 

16 
Mar. 10  MidTerm Exam  
Mar. 15,17  No Class  SPRING BREAK  
17 
Mar. 22 
Proof of the SchwartzZippel
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 
GoldreichLevin 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 MAXSAT 

25 
Apr. 26, 28 
NP in PCP(poly(n),1) 

27 
Apr. 2829 
EndTerm
Exam (Take Home) 