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.