CS 579: Computational Complexity

Course Description

Computational complexity is a central area of theoretical computer science, where we seek to understand and quantify the fundamental limits of computation. We study how different resources—such as time, space, randomness, nondeterminism, proofs, quantum states, interaction, and computational models—shape what can and cannot be efficiently computed. The field connects deeply with many other areas, including coding theory, pseudorandomness, expansion, cryptography, and mathematics. Despite decades of groundbreaking progress and many beautiful results, some of the most profound questions remain unresolved—such as the status of P vs. NP, stronger circuit lower bounds, the role of randomness, and more powerful forms of the PCP theorem.

This advanced graduate course takes students from the foundations of computational complexity to selected topics at the research frontier. Along the way, the goal is not only to convey knowledge, but also to help students cultivate research maturity—learning how to identify important questions, appreciate powerful techniques, and engage with the excitement of open problems that continue to shape the field.

Lectures

• Lecture 1 (26 Aug): A Glimpse of Computational Complexity.
• Lecture 2 (28 Aug): Part 1: Space-bounded computation, Savitch's theorem, L vs NL. Part 2: Introduction to Boolean Fourier analysis.
• Lecture 3 (02 Sep): TBD
• Lecture 4 (04 Sep): TBD
• Lecture 5 (09 Sep): No class (Oberwolfach workshop). Assigned video: Expanders survey by Wigderson. Further reading: Expander Graphs and Their Applications survey by Hoory, Linial and Wigderson.
• Lecture 6 (11 Sep): No class (Oberwolfach workshop). Assigned video: List and local decoding by Guruswami. Further reading: Essential Coding Theory book by Guruswami, Rudra and Sudan.
• Lecture 7 (16 Sep): TBD

Grading

The primary goal of this course is to help you develop research maturity and increase your knowledge and skills. Grades will be a secondary concern. However, we do expect you to seriously engage with your chosen research project and complete all assigned homework.

Policy

• Project: 60% (graded out of 70%, with up to 10% extra credit)
  • This will consist of selecting a research problem or paper related to the course in consultation with the instructor. Students can either work in pairs (strongly encouraged) or individually. The outcome will be a research paper on the chosen topic, along with a mandatory presentation (20% of the project grade) towards the end of the course. The project will have the following deadlines:
    • Deadline 1 (October 5th): 5-page document describing your chosen research problem together with a brief literature review (10%).
    • Deadline 2 (November 1st): 7-page document describing ideas to attack your research problem, with a preliminary discussion of expected opportunities and pitfalls (10%). You may change your research project up to this point if needed.
    • Deadline 3 (December 1st): 10-page document with a more mature and detailed discussion of your attempts to solve the problem, results (if any), challenges, related questions, conjectures, etc. (10%).
    • Deadline 4 (December 15th): A mandatory polished 15-page research paper (20%).
• Homework: 30%
  • You may work in pairs or trios. For each deadline below, choose any 2 new chapters of the Arora–Barak book and solve at least 20% (if in pairs) or 30% (if in trios) of the exercises. Each homework carries equal weight. (For CS PhD students, this may be a good time to start preparing for the complexity qualifying exam.)
    • Deadline 1: September 20th
    • Deadline 2: October 20th
    • Deadline 3: November 20th
• Participation: 10%
  • Scribing 1-2 lectures (with high-quality notes from additional reading/research/references with a 8 days deadline from the lecture) in pairs (ideally, a PhD student + masters/udergraduate), attendance, asking questions, curiosity, and general engagement.
  • LaTex template for scribers here (adapted from Luca Trevisan's template)

Material

The book "Computational Complexity: A Modern Approach" by Arora and Barak is the closest reference for the material we will cover in this course.

Complexity Zoo

A good guide for the vast Zoo of complexity classes: Complexity Zoo

Open Problems In Honor of Luca Trevisan

An Open Problems Column in honor of Luca Trevisan by Fortnow, Goldreich, Håstad, Vadhan and Williamson (edited by Gasarch).

Pre-requisites

Linear algebra, probability theory, complexity theory & algorithm design (at the undergraduate level), and mathematical maturity will be assumed. If some of this background is missing, the course may feel more intense, but it may be still ok to take the course. Talk with the instructor for additional reading and learning material.