Courses of Study 2022-2023 
    
    Dec 04, 2022  
Courses of Study 2022-2023
Add to Favorites (opens a new window)

CS 6810 - [Theory of Computing]


     
Fall. Not offered: 2022-2023. Next offered: 2023-2024. 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)