Show The Graduate Center Menu

Theoretical Computer Science

Instructor: Associate Professor Noson Yanofsky

  • Homework Recitation: For one hour after class.

  • Office: 1430N (Brooklyn College)


  • Required text:

    • Computational Complexity: A Modern Approach
      Sanjeev Arora and Boaz Barak.
      Cambridge University Press. (Please get this book before the first day of class and start reading.)

  • There will be hand-outs from:

    • The Outer Limits of Reason: What Science, Mathematics, and Logic Cannot Tell Us
      Noson S. Yanofsky.
      MIT Press.


  • Midterm: 40%

  • H.W.: 10%

  • Presentation : 10%

  • Final: 40%

Couse Content & Work

We will cover the first 7 chapters of the CC book. Every student will also have to make a presentation on one of the other chapters in the book. These presentations will be at the end of the semester.

There will be homework every single week. You must hand in the H.W. at the beginning of the next class. The midterm and final questions will be similar to the H.W. questions.

Learning Outcomes

  • Show equivalence of different kinds of Turing Machines

  • Prove undecidability of computational problems

  • Classify decision problems into appropriate complexity classes, including P, NP, PSPACE and complexity classes based on randomized machine models and use this information effectively.

  • State precisely what it means to reduce one problem to another, and construct reductions for simple examples. Prove NP-completeness, PSPACE-completeness, and NL-completeness results through reductions

  • Prove results that involve relativization and randomization

  • Classify optimisation problems into appropriate approximation complexity classes and use this information effectively.

  • Use the concept of interactive proofs in the analysis of optimisation problems.

  • Explain the notions of interactive proofs, lower bounds, cryptosystems, etc.