CS 6810

Last Updated

  • Schedule of Classes - January 15, 2024 7:50PM EST
  • Course Catalog - January 15, 2024 7:28PM EST

CS 6810
Theory of Computing

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