CSE 6321 - Computability and Complexity

Spring 2016

Thought provoking links:

Announcements:

Notes on the complexity of optimization problems.

Textbook:

Recommended reading:

• Computational Complexity. C. Papadimitriou.
• Computational Complexity: A Modern Approach. Sanjeev Arora and Boaz Barak (free draft available).

Syllabus:

Office hours:

By grader: Jiaqi Liu

(liu.1639@buckeyemail.osu.edu)

Tue 11:00-12:00noon in Dreese Labs 778.

Problem Sets:

PS1 (due beginning of lecture on January 28th). Solutions.
PS2 (due beginning of lecture on February 16th). Solutions.
PS3 (due beginning of lecture on February 25th). Solutions.
PS4 (due beginning of lecture on March 10th). Solutions.
PS5 (due beginning of lecture on March 29th). Solutions.
PS6 (due beginning of lecture on April 14th). Solutions.
PS7 (due beginning of lecture on April 21st). Solutions.