CS 6810

CS 6810

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

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

  •   Regular Academic Session. 

  • 4 Credits Stdnt Opt

  • 18165 CS 6810   LEC 001

    • TR Statler Hall 351
    • Aug 26 - Dec 7, 2021
    • Chattopadhyay, E

  • Instruction Mode: In Person
    Seats are reserved for graduate students. Professional and undergraduate students should add themselves to the waitlist during add/drop. See enrollment page for more details: https://www.cs.cornell.edu/courseinfo/enrollment/cs-6000-level-courses