
CPSC 506101 Page, Fall 2008
This page concerns CPSC 506 Section 101, for Winter 200809 term I
(i.e., Fall 2008).
This page has the most uptodate 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
JinYi 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 200607.
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 email 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 RazborovRudich). We will study Hastad's article:
The Shrinkage Exponent of DeMorgan Formulas is 2, SIAM Journal on Computing,
1998, Vol 27, pp4864. 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) ). 
