Spring'26: Complexity of Computation and Hardness of Approximation (CS 538)Busch Campus Instructor: Karthik C. S. This is a graduate course in computational complexity theory. The course will place special emphasis on providing context and intuition for the material covered. For the first half of the course, we will follow Goldreich's textbook; for the second half, we will use various surveys, research articles, and lecture notes. Prerequisites: It will be helpful to have some background in algorithms and/or discrete mathematics, but no formal prerequisite will be enforced. If you do not satisfy the official prerequisites but are still interested in registering for the course and are concerned about being sufficiently prepared, please send me an email. The only real prerequisite is some mathematical maturity. Grading: To pass the course, you must satisfy both of the following requirements: (1) You must get at least 7 questions completely correct in Homework 1. The homework is due on February 1. (2) You must attend at least 9 out of the first 12 lectures. Each student must either present a 1-hour lecture or submit a detailed report at the end of the course. Your entire grade will be based on this component (conditional on meeting the two passing criteria above). You will work with the instructor throughout the course to make progress on your lecture/report. Topics and schedule
|