CSE 532: Computational Complexity II, Spring 2007

CSE Home

About Us

Search

Contact Info

Email   Archive    Sign-up Instructions Problem Sets   Problem Set #1   Problem Set #2 Lectures   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.