The Steam Powered Turing Machine University of Washington Department of Computer Science & Engineering
 CSE 532: Computational Complexity II, Spring 2007
  CSE Home  About Us    Search    Contact Info 

  Sign-up Instructions
Problem Sets
  Problem Set #1
  Problem Set #2
  All lectures
  Lecture 1
  Lecture 2
  Lecture 3
  Lecture 4
  Lectures 5-6
  Lecture 7
  Lecture 8
  Lecture 9
  Lecture 10
  Lecture 11
  Lecture 12
  Lecture 13
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:

  • The complexity of counting: #P and the polynomial-time hierarchy.
  • Concrete (combinatorial) computational models including circuits, communication complexity, decision trees, and branching programs. Relationship to polynomial-time hierarchy. Parallel complexity classes based on circuit families. Constructions and lower bounds in these models. The limitations of these "natural proof" methods for lower bounds.
  • Time-space tradeoff lower bounds.
  • Space-bounded pseudo-random generators and the space complexity of connectivity.
  • The PCP Theorem. Overview of the proof and implications for hardness of approximation.
  • Fourier analysis of Boolean functions and its applications.
Possible additional topics: Overview of proof complexity, cell-probe model for data structures.

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.

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: © 1993-2007, Department of Computer Science and Engineering, University of Washington.