Graduate Course Descriptions

The following directory lists the graduate courses which the University expects to offer, although the University in no way guarantees that all such courses will be offered in any given academic year, and reserves the right to alter the list if conditions warrant. Click on the links below for a list of courses in that subject area. You may then click “View Classes” to see scheduled classes for individual courses.

5506. Computational Complexity

3.00 credits

Prerequisites: Prerequisite: Open to graduate students in the CSE program, others with permission. Recommended preparation: CSE 3502 and 3500; MATH 3160 or the equivalent. (RG5908)

Grading Basis: Graded

Systematic study of resource-bounded computation, including time and space complexity, hierarchy theorems, nondeterministic and randomized computation, and reduction and completeness. Advanced topics may be introduced such as relativized computation, derandomization, communication complexity, lower bounds on circuit complexity, and probabilistically checkable proofs.

No classes found.