CSE 540 - Theory of Computation (Graduate level) - Spring 2024

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 

• Week 1: Turing Machine and P vs NP. 

• Week 2: NP-completeness. 

• Week 3: More on NP and some on DTIME. 

• Week 4: Space complexity. 

• Week 5: Non-Deterministic Space. 

• Week 6: The structure of NL. 

• Week 7: Randomized Computation. 

• Week 8: Non-Uniform Polynomial-Time (P/poly). 

• Week 9: The Polynomial-Time Hierarchy. 

• Week 10: Interactive Proofs. 

• Week 11: Probabilistically Checkable Proofs (PCP). 

• Week 12: Quantum Computing and BQP, QIP, QMA, QCMA.

Prerequisite

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

Textbooks

• Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak,

• Computational Complexity by Christos Papadimitriou.

Evaluation

• 60% In-class open book midterm,

• 30% Project (presentation+ viva after the presentation)

• 10% Scribe 

Piazza

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

Office hour

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