CPSC 506-201 Page, Spring 2007
This page concerns CPSC 506 Section 201, for Winter 2006-07 term II (i.e., Spring 2007).
This page has the most up-to-date information on the course and supersedes any other document.
This course studies the interplay between various computational resources required of algorithms; these resources include space, time, randonmess, and nondeterminism. We use the notions of complexity theory, including classes such as P, NP, NC, PSPACE, RP, BPP, #P, etc., and the relationships between them. We shall primarily follow notes from Steven Rudich's complexity theory class taught in 2000, although we will spend more time on certain topics and skip or briefly mention others. Professor Rudich's course website contains additional material.
For the second part of the course we will also use two more terrific sources: material on lower bounds by Stasys Jukna meant to supplement his book on Extremal Combinatorics, and a draft of a book on complexity theory by Sanjeev Arora and Boaz Barak; see also Arora's CS 522, Spring 2001, lecture 22 notes on Natural Proofs.