CSE204 - Computational Complexity

Course Basics

Class: Tu/Th, 11:40AM - 1:15PM
Location: Physical Sciences, 136

Instructor: C. (Sesh) Seshadhri (sesh@)
Office hours: Tue, 10:15-11:15

Course Description

Graduate computational complexity. We will cover space complexity, the polynomial hierarchy, randomized complexity classes, the concept of interactive proofs, and maybe the basics of cryptography. Students should be familiar with the content of CSE103 (basic theory of computation), and must be comfortable in writing proofs in Latex.

Material from Similar Course

I taught a version of this course as CSE104 in 2020. The course website for CSE104 has many of the notes I will use, and there are links to all lecture videos. Feel free to use the material there are as a resource. I will link relevant notes and videos in the schedule page. The current course (CSE204) will be a faster version of CSE104, so that there is time left over for more advanced topics.

Course Textbook

We will follow Computational Complexity: A Modern Approach by Arora and Barak. A draft of the book is also publicly available. We will cover up to Chapter 8 or 9.