CSCI 2560 - Advanced Complexity

Instructor: Anna Lysyanskaya

Location: CIT345

Meeting time: TTh 10:30-11:50

Description: Advanced topics in computational complexity, such as: the polynomial hierarchy, interactive proofs, pseudorandomness, derandomization, probabilistically checkable proofs.

Textbook: Complexity Theory: A modern approachSanjeev Arora and Boaz Barak.


Schedule

 Lecture #  Topic  Presentation  Homework
 1  Ch 1  Anna  
 2  Ch 2  Anna  Administrivia
 3  Ch 5   Anna  Pr. 2.27, 2.28
 4  Ch 6  Anna  
 5  Ch 7  Patrick  Pr. 7.6, 7.8
 6  Ch 8  Anna + Foteini  Pr. 8.1, 8.3
 7  Ch 8  Anna + Foteini  
 8 HW Everyone 
 9  Ch 8  Anna   
 10  Ch 8  Anna   
 11 Ch 13  Sasha + Foteini  
 12 Ch 11   Feng-Hao
13Ch 14 Anna Administrivia 
14 HW Everyone
Pr. 11.1, 11.2, 11.4, 11.6,  13.1, 13.514.1 
15 Ch 14  Anna  
16Ch 15 Sasha Pr 15.1
17Ch 15 &  Ch 19 Sasha + Huanzhong 
18 Ch 19 Huanzhong 
19  Ch 20 Sasha + Foteini 




Comments