Courses of Study 2021-2022 
    
    Mar 29, 2024  
Courses of Study 2021-2022 [ARCHIVED CATALOG]

Add to Favorites (opens a new window)

CS 4814 - [Introduction to Computational Complexity]


     
Spring. Not offered: 2021-2022. Next offered: 2022-2023. 3 credits. Student option grading.

Prerequisite: CS 4820 .

E. Chattopadhyay.

Explores the power and limitations of efficient computation. Understanding how the notion of efficient computation changes with respect to resources such as time, space, randomness, advice, and interaction. Concrete computational models that we will study will include Turing machines, Boolean circuits, Decision trees, and Branching Programs. Advanced topics may include error-correcting codes, probabilistic checkable proofs, and circuit lower bounds.



Add to Favorites (opens a new window)