CPSC 506-101 Page, Fall 2008

This page concerns CPSC 506 Section 101, for Winter 2008-09 term I (i.e., Fall 2008).

This page has the most up-to-date information on the course and supersedes any other document.

The focus of this course is the P vs. NP problem. More broadly we will study aspects of complexity theory, the interplay between various computational resources required of algorithms; these resources include space, time, randonmess, and nondeterminism. This interplay is often stated in terms of complexity classes, such as DTIME(f(n)), NTIME(f(n)), DSPACE(f(n)), NSPACE(f(n)), RTIME(f(n)), etc., for a variable function, f, and in particular 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. Another excellent source for basic complexity theory is Jin-Yi Cai's notes.

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
CS506 from Spring 2007	The Fall 2008 CPSC 506 will be very similar (but not identical) to the CPSC 506 course I gave in 2006-07. Here are those materials; they include notes which I'll refer to and use (although there may be omissions, new material, and possibly some reworked material). Here are some of my notes for class for this year; they are in random order, and in plain text (and therefore look horrid); use at your own risk: not all this stuff will be covered in class, and some may change.
Homework	Homework problems will be assigned during class and collected periodically. Here is Homework 1. Here is Homework 2, which is a work in progress at present.
Office Hours	I will hold office hours by appointment (for as long as this is feasible); just e-mail me and tell me when you are free to meet. During hectic times I may revert to limited office hours at fixed times.
Other News	The main new topic this year is formula size complexity (which will replace a discussion of Razborov-Rudich). We will study Hastad's article: The Shrinkage Exponent of DeMorgan Formulas is 2, SIAM Journal on Computing, 1998, Vol 27, pp48-64. This gives explicit functions in NP with formula size roughly at least n^3, which is the best such result to date. This article is available, for example, from Hastad's homepage (see the copyright notice) or from SIAM Journal on Computing; as fas as I know, it can be read entirely from what we know (e.g., we know that there exist functions on k Boolean variables of minimum formula size roughly 2^k/log(k) ).