CS 5814

Last Updated

  • Schedule of Classes - June 16, 2025 11:41AM EDT
  • Course Catalog - September 10, 2024 9:48AM EDT
Global toggle of class tabs

Links for textbooks and Cornell Store open in new tab.

CS 5814
Introduction to Computational Complexity

Course information provided by the 2024-2025 Catalog. Courses of Study 2024-2025 is scheduled to publish mid-June.

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/Corequisites Prerequisite: CS 4820. 

Last 4 Terms Offered (None)

When Offered Fall.

View Enrollment Information

Syllabi: none

  •   Regular Academic Session.  Combined with: CS 4814

  • 3 Credits Graded

  • 19636 CS 5814   LEC 001

  •  

  • Instruction Mode: In Person

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