CS 4814

Last Updated

  • Schedule of Classes - September 9, 2021 7:14PM EDT
  • Course Catalog - September 9, 2021 7:15PM EDT

CS 4814
Introduction to Computational Complexity

Course information provided by the Courses of Study 2020-2021.

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.

When Offered Spring.

Prerequisites/Corequisites Prerequisite: CS 4820.

View Enrollment Information

Syllabi: none

  •   Regular Academic Session. 

  • 3 Credits Stdnt Opt

  • 11856 CS 4814   LEC 001

  •  
    • TR Ives Hall 305
    • Feb 8 - May 14, 2021

    • Chattopadhyay, E

  • Instruction Mode: In Person
    Enrollment limited to CS students only. All others may add themselves to the waitlist during add/drop. Please go to http://www.cs.cornell.edu/courseinfo/enrollment for updates.
    Enrollment limited to students who are able to attend in-person classes in the Ithaca area.

Syllabi: none

  •   Regular Academic Session. 

  • 3 Credits Stdnt Opt

  • 18065 CS 4814   LEC 002

  •  
    • TR Online Meeting
    • Feb 8 - May 14, 2021

    • Chattopadhyay, E

  • Instruction Mode: Online
    Enrollment limited to CS students only. All others may add themselves to the waitlist during add/drop. Please go to http://www.cs.cornell.edu/courseinfo/enrollment for updates.