Computer Science 522
Advanced Complexity Theory

Spring 2014

Sanjeev Arora

   HOMEWORKS

   Remember: most proofs will fit in a paragraph or two. Collaboration with classmates is permitted and encouraged.

1. HW 1: Due Tues Feb 25 in class. Questions 2.9, 2.22, 2.30, 3.2, 3.3., 3.4, 5.1.
2. HW 2: Due Thurs Mar 6 in class. Questions 4.5, 4.9, 5.6, 5.9, 6.3, 6.5, 6.18, 7.5, 7.7, 7.8. 
3. HW 3: Due Thurs Mar 27 in class. Questions 8.5, 8.8 8.10, 10.8, 10.5,  10.11
   
4. HW 4: Due Date April 17 in class. Questions 19.2, 19.4, 19.7, 20.4, 20.6, 14.2, 14.3, 14.7.