CSE532: Computational Complexity II

Catalog Description: Advanced computational complexity including several of the following: circuit complexity lower bounds, #p and counting classes, probabilistically-checkable proofs, de-randomization, logical characteristics of complexity, communication complexity, time-space tradeoffs, complexity of data structures.

Prerequisities: (none listed)
Credits: 4.0

Portions of the CSE532 web may be reprinted or adapted for academic nonprofit purposes, providing the source is accurately quoted and duly credited. The CSE532 Web: © 1993-2024, Department of Computer Science and Engineering, University of Washington. Administrative information on CSE532 (authentication required).