CS 6810

Last Updated

  • Schedule of Classes - October 31, 2025 7:07PM EDT

CS 6810
Theory of Computing

Course information provided by the 2025-2026 Catalog.

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.


Prerequisites CS 4810, CS 4820 or CS 4814, or permission of instructor.

Last 4 Terms Offered 2023FA, 2021FA, 2017SP, 2016SP

View Enrollment Information

Syllabi: none

  •   Regular Academic Session. 

  • 4 Credits Stdnt Opt

  • 15880 CS 6810   LEC 001

  •  
    • TR
    • Jan 20 - May 5, 2026

    • Chattopadhyay, E

  • Instruction Mode: In Person

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