Computational Complexity
Welcome to this course! Computational complexity theory focuses on understanding the fundamental limitations and capabilities of efficient computation. For example, which computational problems inherently require a huge amount of computational resources to solve, no matter how clever the algorithm is? Typical resources include running time, running space/memory, and randomness. The most basic question of computational complexity is how to classify computational problems according to their difficulty.
In this course, we will introduce some complexity classes, including P, NP, BPP, P/poly, and IP. We will also learn connections between complexity classes, and how to classify problems into appropriate classes. This course might be interesting to graduate students or advanced undergraduates, and in particular, those who plan to do research in theoretical computer science.
General Information:
Instructor: Jiapeng Zhang. ( jiapengz@usc.edu )
Time: Friday 1:00 - 4:20 pm
Office hours: by appointments
Location: GFS 213.
Piazza: link.
Textbook:
We will use the book Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak.
Grading:
Three homework sets, each worth 20%. The homework can be done in a group of at most three students.
One take-home final exam which is worth 40%.