
CSE Home  About Us  Search  Contact Info 
CSE 532: Computational Complexity II
TTh 10:3011:50 CSE 403 Instructor: Paul Beame Catalog Description: Advanced computational complexity including several of the following: circuit complexity lower bounds, #P and counting classes, probabilisticallycheckable proofs, derandomization, logical characteristics of complexity, communication complexity, timespace tradeoffs, complexity of data structures. Recommended preparation: CSE 531 Specifically, we will cover/survey many of the major recent developments in computational complexity not already covered in CSE 531 including:
There is a draft textbook by Sanjeev Arora and Boaz Barak, Complexity Theory: A Modern Approach that covers much of the content of the course. Background: Note that CSE 531 is recommended but not essential preparation. All that is needed is familiarity with the basic concepts of time and space complexity for Turing machines and the notions of reductions and completeness. We will review the necessary properties of the polynomialtime hierarchy that were covered in CSE 531. Portions of the CSE 532 Web may be reprinted or adapted for academic nonprofit purposes, providing the source is accurately quoted and duly credited. The CSE 532 Web: © 19932007, Department of Computer Science and Engineering, University of Washington. 