CS 6810

CS 6810

Course information provided by the Courses of Study 2023-2024.

Computational complexity theory is devoted to understanding the limitations of efficient computation (with respect to computational resources such as time, space and randomness). This course will be a graduate level introduction to various aspects of complexity theory, with basics topics including time/space complexity, NP completeness, and the polynomial hierarchy, and advanced topics such as the PCP theorem, randomness and derandomization, circuit lower bounds, etc.

When Offered Fall.

Prerequisites/Corequisites Prerequisite: CS 4810, CS 4820 or CS 4814, or permission of instructor.

View Enrollment Information

Syllabi: none
  •   Regular Academic Session.  Choose one lecture and one project.

  • 4 Credits Stdnt Opt

  • 19447 CS 6810   LEC 001

  • Instruction Mode: In Person
    Restricted to Ithaca campus graduate students only. Undergraduate and MEng students must add themselves to the waitlist during add/drop. This course is not available to Cornell Tech students.

  • 19592 CS 6810   PRJ 601

    • TBA
    • Aug 21 - Dec 4, 2023
    • Chattopadhyay, E

  • Instruction Mode: In Person