CS 4814

Last Updated

  • Schedule of Classes - April 14, 2026 7:07PM EDT

CS 4814
Introduction to Computational Complexity

Course information provided by the 2026-2027 Catalog.

Explores the power and limitations of efficient computation. Understanding how the notion of efficient computation changes with respect to resources such as time, space, randomness, advice, and interaction. Concrete computational models that we will study will include Turing machines, Boolean circuits, Decision trees, and Branching Programs. Advanced topics may include error-correcting codes, probabilistic checkable proofs, and circuit lower bounds.


Prerequisites CS 4820.

Last 4 Terms Offered 2024FA, 2021SP, 2020SP, 2015FA

View Enrollment Information

Syllabi: none

  •   Regular Academic Session.  Combined with: CS 5814

  • 3 Credits Stdnt Opt

  • 17874 CS 4814   LEC 001

  •  
    • TR
    • Aug 24 - Dec 7, 2026

    • Kim, M

  • Instruction Mode: In Person

    For Bowers Computer and Information Science (CIS) Course Enrollment Help, please see: https://tdx.cornell.edu/TDClient/193/Portal/Home/