Courses of Study 2021-2022 
    
    Sep 22, 2021  
Courses of Study 2021-2022
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)