|CSE Home||About Us||Search||Contact Info|
CSE 532: Computational Complexity II
TTh 10:30-11:50 CSE 403
Instructor: Paul Beame
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. 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 polynomial-time hierarchy
that were covered in CSE 531.