COMS 4236

Introduction to Computational Complexity


Many computational problems (such as multiplying two numbers, or sorting a list of numbers) are known to be "easy" in the sense that we have efficient algorithms for them. Unfortunately, many other computational problems of great practical importance (such as factoring large numbers, or finding the shortest tour that passes through all the cities on a map) seem to be difficult, in the sense that no efficient algorithms are known. Are these problems really inherently difficult -- do no efficient algorithms exist? -- or do we just need to come up with cleverer algorithms that can solve these problems efficiently?

Questions such as these lie at the heart of computational complexity, which is the study of the inherent abilities and limitations of efficient computation. Computational complexity is one of the most fundamental and important topics in computer science; indeed, the core question of computational complexity theory ("does P equal NP?") is one of the most famous and important open questions in all of computer science and mathematics.

Quick Links

General Information

Instructor: Rocco Servedio

Instruction modality: On campus, in Mudd 524. Throughout the semester lectures will be recorded and recordings will be made available to all enrolled students through Courseworks. That said, you are strongly encouraged to come to class in person (there is a strong historical correlation between coming to class in person and doing well in the course).

Time: Mon/Wed 8:40am-9:55am Eastern Time

Course email (for administrative issues; use Ed Discussion for subject matter questions): coms4236columbiaS23 at gmail dot com

List of Topics

This is a preliminary list of core topics. Other topics may be covered depending on how the semester progresses. Most topics will take several lectures. For more information, click on the "Lectures" tab above.

  • Intro to topic; computational problems; Turing Machines; time complexity and P; nondeterminism and NP; Cook-Levin theorem and NP completeness. Note: Coming into the class, you are expected to be familiar with the basics of Turing Machines, nondeterminism, and NP completeness, at the level of Chapters 3 and 7 of the Sipser textbook.
  • Oracles and the polynomial time hierarchy
  • Hierarchy theorems, basic reslationships among resources
  • Space classes (PSPACE, L, NL)
  • Randomness as a computational resource, associated complexity classes
  • Complexity of counting (exact and approximate)
  • Communication complexity
  • Circuit complexity: circuits, formulas, lower bounds for constant-depth circuits
  • Interactive proofs, IP=PSPACE, Probabilistically checkable proofs (PCP), and inapproximability