## Results for CS254 |
2 courses |

An introduction to computational complexity theory. Topics include the P versus NP problem and other major challenges of complexity theory; Space complexity: Savitch's theorem and the Immerman-Szelepscényi theorem; P, NP, coNP, and the polynomial hierarchy; The power of randomness in computation; Non-uniform computation and circuit complexity; Interactive proofs. Prerequisites: 154 or equivalent; mathematical maturity.

Terms: Win
| Units: 3

A continuation of CS254 (Computational Complexity). Topics include circuit complexity, proof complexity, communication and information complexity, average-case complexity, and complexity barriers. Prerequisite: CS 254.

Terms: Spr
| Units: 3

Instructors: ; Tan, L. (PI)