CSE 540 - Theory of Computation (Graduate level) - Fall 2024
Instructor: Supartha Podder
Lectures: Monday Wednesday 5:00PM - 6:20PM
Location: FREY HALL 216 WEST CAMPUS (map)
Office Hour & Location: Wednesday 12:30PM - 2:30PM at NCS 151 or online
https://calendar.app.google/LsAEkivZNshjTexS6
Instructor: Supartha Podder (supartha@cs.stonybrook.edu)
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-8: Randomized Computation.
Week 9: Non-Uniform Polynomial-Time (P/poly).
Week 10: The Polynomial-Time Hierarchy.
Week 11: Interactive Proofs.
Week 12: Probabilistically Checkable Proofs (PCP).
Week 13: Quantum Computing and BQP, QIP, QMA, QCMA.
Week 14-15: TBD
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
The grading will be based on the following criteria:
Midterm Exam (open book): 40%
Final Exam (open book): 50%
Scribe: 10%
Surprise class test: Bonus 10%
Piazza
signup link: https://piazza.com/stonybrook/fall2024/cse540
Office hour
Wednesday 12:30-2:30pm https://calendar.app.google/LsAEkivZNshjTexS6
