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, 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 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 alone).

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 uncountability).

Announcements	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	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.
Paper/Project	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).
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.
GCT Notes	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 toy examples; 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 periodically.
More Materials	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 here, without the fluff; 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 related problems, by Ketan D. Mulmuley and Milind Sohoni. (Can anyone recommend other articles about this approach?)
Notes	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.
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