CPSC 506-101 Page, Fall 2008
THIS PAGE IS UNDER CONSTRUCTION!!!
This page concerns CPSC 506 Section 101, for Winter 2012-13 term I
(i.e., Fall 2012).
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,
interplay between various computational resources
required of algorithms; these resources include space, time, randonmess,
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
We shall begin with the following classical topics in complexity
theory, all regarding P vs. NP:
P, NP, the polynomial time hierarchy; separation of various DTIME
classes (via diagonalization); Baker-Gill-Soloway theorem (why
P versus NP cannot be solved by diagonalization and similar techniques
Hopefully we will at least 3-4 weeks on some relatively recent
approach to P versus NP or why certain approaches probably won't work;
barring this, we may have a look at the same for a difficult question in
circuit complexity (may not be worth $1,000,000, but would still get
you a nice job).
Background: I assume that either (1) that you are familiar with
the material in a first theory course, such as CPSC 421
(i.e., P, NP, NP-completeness, uncomputability, Cook-Levin theorem,
etc.), or (2) are
willing to read up on any such material in Arora-Barak
(this material is typically covered in a month of an undergraduate
class, and may not
be difficult for, say, someone studying math who has seen many
of these ideas in a different context, such as diagonalization and
Class meets Mondays and Wednesday, 9:30am-10:50am, in Dempster 101.
First meeting is Wednesday, September 5, 2012.
Everyone is welcome to attend; if you are not a Computer Science grad
student and you wish to take the course for a grade, you may need to
fill out some form (but there should be plenty of space in the course).
Homework problems: Four homework problems at the bottom of
September 17 notes.
From the text: 3.4, 3.7, 3.8, 16.1, 16.3, 16.6.
You may write a paper/project on any topic related to this course.
You can choose a topic that we haven't covered in class from Arora-Barak,
for example, or choose one of your own. Such topics would include:
expanders, extractors, cryptography, Levin's average case complexity,
natural proofs, communication complexity, n^2 permanent vs. determinant
lower bound, more on Geometric Complexity Theory, Yao's Lemma (12.4 of text).
For much of the course we will use the
text, Computational Complexity Theory: A Modern
Approach, by Arora and Barak.
It is available from the bookstore, and is free online (viewing one subsection
at a time, unfortunately)
to the UBC community via the library (via books24x7)
at this location
(click on the word "Book" in the middle of the page; you may have to
enter some sort of UBC identification).
Aside from this text, we will refer to articles available online.
A secondary source is
an article that I am writing
on "Geometric Complexity Theory," a term coined by
Mulmuley and Sohoni to describe their intriguing (but
at present speculative)
approach to obtaining new lower bounds.
Our description does not assume any algebraic geometry.
It is easy to play around with
however, to apply it to any of the well-known open problems
in complexity gets more difficult (and, at present, more speculative).
This article is a work in progress and will be updated
More materials along the lines of this course can be found on
Alexandra Kolla's CS579 website.
Aside from the text we might make use of the following articles (depending
on how much time we have):
Completeness Classes in Algebra,
by Leslie Valiant, 1979;
Understanding the Mulmuley-Sohoni Approach to P vs. NP,
by Kenneth W. Regan, 2002;
The GCT Program Toward the P vs. NP Problem,
by Ketan D. Mulmuley, 2012 (thank Ives and Nick), or
On P vs. NP, Geometric Complexity Theory, and the Riemann Hypothesis,
by Ketan D. Mulmuley;
Geometric Complexity Theory I: An approach to the P vs. NP and
by Ketan D. Mulmuley and Milind Sohoni.
(Can anyone recommend other articles about this approach?)
I am making some brief notes for myself. They may be helpful to give
more details on what we will cover; however, you may just find them
confusing. You are welcome to have a look, but do so at your own risk...
Notes made on September 4;
for two or three classes.
Notes made for class starting September 10.
Notes made for class starting September 17.
Notes made for class starting September 24.
Notes made for class starting October 1.
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.