CS 6520 - Computational Complexity

Spring 2008

[Syllabus] [Recommended Textbooks] [Announcements] [Lectures] [Homeworks] [Some Term Paper Topics]

Lectures

Tuesday and Thursday 12:05 - 1:25, Bunger-Henry 311

The material covered in each lecture together with references and/or notes will be posted in the Lectures web page.

Instructor

Yan Z. Ding, ding@cc.gatech.edu

Office: Klaus 3138
Office phone: 404-385-2880
Office hours: TBD

All emails concerning this course should have a subject entitled CS6520.

Administrative Assistant

Dani Denton, denton@cc.gatech.edu
Office: Klaus Building 2132
Phone Number: 404-385-6440

Recommended Textbooks

• Complexity Theory: A Modern Approach by Arora and Barak.
• Complexity Theory: A Conceptual Approach by Goldreich.

Announcements

• 4/24: The term paper is due electronically by Friday, 5/2 at noon.
• 4/7: Problem Set 1 solutions have been posted.
• 3/23: Problem 8 of Problem Set 2 has been modified.
• 3/23: A list of possible topics for the term paper has been posted.
• 3/10: Problem set 2 has been posted.
• 2/28: The statement of problem 3 in problem set 1 was not precise and has been modified.
• 2/28: Questions and answers for problem set 1 can be found here .