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.

Announcements	Feb 16: more problems added (now 15 problems total). More notes added Feb 6.
My notes	My somewhat sketchy notes are available. You might look at them before class, bring them to class to annotate them, and/or supplement them with your own notes. My notes are not intended to be a self-contained, comprehensive reference... :-) First set. Second set. Third set. Fourth set (in progress).
Homework	Homework problems will be assigned during class and collected periodically; first set; second set.
Office Hours	I (Joel Friedman) will hold office hours by appointment (for as long as this is feasible). During hectic times I may revert to limited office hours at fixed times.
Other News