Courses of Study 2021-2022 
    Jul 07, 2022  
Courses of Study 2021-2022 [ARCHIVED CATALOG]

Add to Favorites (opens a new window)

CS 6810 - Theory of Computing

Fall. 4 credits. Student option grading.

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

E. Chattopadhyay.

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.

Add to Favorites (opens a new window)