Instructor: Supartha Podder 

Lectures: Monday Wednesday 9:30AM - 10:50AM

Location: Old CS 2114 WEST CAMPUS (map)

Office Hour & Location: By appointments only Wednesday 1:00PM - 2:00PM at NCS 151  or online  

   Use this link to book an appointment: https://calendar.app.google/sTDBHQfFPYQcHJSf9 

Instructor: Supartha Podder (supartha@cs.stonybrook.edu)

Piazza: https://piazza.com/stonybrook/fall2025/cse540/home

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 lack strong lower bounds that formally prove multiplication is harder in the Turing machine model. 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 1: 30% 

• Midterm Exam 2: 30%

• Project: 30% 

• Scribe: 10% 

University Policies

Disability Support Services

If you have a physical, psychological, medical or learning disability that may impact your course work, please contact Disability Support Services, ECC (Educational Communications Center) Building, room 128, (631) 632-6748 or at sasc@stonybrook.edu. They will determine with you what accommodations, if any, are necessary and appropriate. All information and documentation is confidential.

Academic Integrity

Each student must pursue his or her academic goals honestly and be personally accountable for all submitted work. Representing another person's work as your own is always wrong. Faculty are required to report any suspected instances of academic dishonesty to the Academic Judiciary. Faculty in the Health Sciences Center (School of Health Technology & Management, Nursing, Social Welfare, Dental Medicine) and School of Medicine are required to follow their school-specific procedures. For more comprehensive information on academic integrity, including categories of academic dishonesty, please refer to the academic judiciary website.

AI Use Policy:

We will follow the policy of the department: https://www.cs.stonybrook.edu/students/Policies/aiusage

Critical Incident Management:

Stony Brook University expects students to respect the rights, privileges, and property of other people. Faculty are required to report to the Office of Judicial Affairs any disruptive behavior that interrupts their ability to teach, compromises the safety of the learning environment, or inhibits students' ability to learn. Faculty in the HSC Schools and the School of Medicine are required to follow their school-specific procedures.

Final Grade:

Final grades will be based on how well you've learned the material. Letter grades and grading details (like cutoffs or curves) won't be disclosed or discussed. Please don't ask for comparisons or special treatment. Needing a higher grade or being close to a cutoff might not affect your result. Grades are final and any requests for grade bumps or exceptions will be ignored.

Communication Policy:

The preferred way to communicate is through the course discussion forum piazza - it is the quickest since both the teaching team and your classmates can respond. You're also encouraged to stop by office hours for one-on-one help. If you need to email the instructor or the TA, only use the official email addresses shared in class or on the course website, and always include a clear subject line starting with "[CSE 540]".