CSE 540 - Theory of Computation (Graduate level)

Instructor: Supartha Podder 

One of the most important and central topics in theoretical computer science is to understand whether some problems are harder than others in terms of the amount of computational resources needed to solve these problems. For instance, we still don’t know if addition is inherently easier than multiplication in the Turing machine model. And if yes then why? Computational complexity theory is an area of theoretical computer science which focuses on classifying computational problems according to their inherent difficulty, and relating these classes to each other. 

This course will be an introductory graduate-level course in computational complexity theory. We will begin with the classical results in time and space complexity: Turing machine, time/space hierarchy theorems, introduction to the important complexity classes such as P, NP and PSPACE etc. We will show well known reductions and complete problems. Then, we will study results in randomized model. We will introduce Alternating Turing Machine model and polynomial Hierarchy. In the latter part of the course we will spend significant amount of time in the study of interactive proofs, PCP Theorem and Quantum Computing. We will present the different settings of interactive proofs and show PCP theorem and hardness of approximation. Finally we will introduce quantum computation and show complexity classes arising from the model of quantum computation and study their relationships with well-known complexity classes.

Tentative Schedule 


No prerequisite is required for this course. However knowledge of algorithms, logic, probability theory and theory computation will be a bonus.




signup link: https://piazza.com/stonybrook/spring2024/cse540

Office hour

Thursday 1-2pm and 4:30-4:45pm https://calendly.com/supartha-podder/

CSE 540 Schedule