Math 523-201 Page, Spring 2014

This course gives a self-contained introduction to combinatorial optimization, with a focus on complexity theory. We will use texts available online via the UBC library and notes that I will provide; if you like, you may purchase hardcopies of the texts. We will spend roughly 2/3 of the course on foundations (complexity theory and linear programming), and 1/3 of the course on advanced topics. The advanced topics will depend on the students' interests, but I will be biased towards topics of current research.

Roughly speaking, we will cover the following topics:
  1. Theory of Computation (roughly five weeks). We shall use the textbook Computational Complexity: A Modern Approach, by Arora and Barak (click on "Book", and you will be asked for your CWL). Topics to include (along with Chapters/Sections in Arora & Barak):
    1. Turing Machines (1.1, 1.2),
    2. Uncomputability (1.5),
    3. P (1.6) and NP (2.1),
    4. Cook's Theorem (2.3) and NP-complete problems (2.4, perhaps 2.2),
    5. Algebraic complexity (16.1),
    6. Randomized complexity (7.1--7.3).

  2. Linear Programming (roughly three weeks). We shall use the textbook Linear Programming: Foundations and Extensions, by Vanderbei (click on "Book", and you will be asked for your CWL). Topics to include (along with Chapters/Sections in Vanderbei):
    1. Application (before we give the theory): Two person zero sum games (11.1--11.3),
    2. Linear programs (1.2) and the simplex method (2.1--2.4) and the perturbation method (3.3),
    3. Duality (5.1--5.4) and complementary slackness (5.5),
    4. Application: Yao's Theorem on Randomized Computation (Arora and Barak, 12.4.1).

  3. Advanced topics, to be chosen from (based, in part, on a student poll):
    1. The "Permanent versus Determinant" question (Arora and Barak, 16.1), as an algebraic analogue of P versus NP;
    2. Other interesting questions/bounds in complexity theory;
    3. Other applications in linear programmig;
    4. A quadratic lower bound for the "Permanent versus Determinant" question;
    5. An introduction to the Mulmuley-Sohoni method ("Geometric Complexity Theory") regarding Permanent versus Determinant (and P versus NP); here are notes of mine from a few years ago (I may add more examples that I gave in CS506); this is the only currently tenable approach to P versus NP and related problems of which I am aware.
News Final projects will be graded on Wednesday, April 23, 2014; please submit your project earlier if possible. Class on April 4 and 7 will be on the determinant and Geometric Complexity Theory.
Project Final projects will be graded on Wednesday, April 23, 2014; please submit your project earlier if possible. Your project should be expository, including motivation, precise definitions and statements of theorems and/or open problems, and an overview of the proofs and tools involved; you might imagine you are giving a lecture or two on the topic. They should be 3 to 5 pages long, with an additional appendix, if you like, giving more details. Some possible ideas for a final project (i.e., paper) are here. Here is a sample project that is a bit too long, which is essentially the article on formula and circuit complexity; another good example is article which are notes of mine from a few years ago on Geometric Complexity Theory.
Blogs I am keeping some "blogs," which are set of notes (text files) meant to supplement the texts and say roughly where we are at any particular week or so.
"blog1, for Jan 6 to Jan 22" covers the classes Jan 6 to Jan 22, roughly Chapter 1, first section of Chapter 3 (3.1), and the start of Chapter 2 (definition of NP).
"blog2" begin with Chapter 2, starting on Jan 24. Starting February 7, we began discussing formulae and circuits; see this summary and blog2 (which covers parts of Chapter 16 of the text).
"blog3" starting March 3, describes our coverage of Linear Programming (start using Vanderbei's text).
"blog4" starting April 4 describes our coverage of complexity theory beyond the textbooks: Valiant's construction, and an introduction to Mulmuley-Sohoni's Geometric Complexity Theory. Valiant's construction is now at the end of the summary on formulas and circuits.
Here is STOC 1979, where you can find Valiant's article, Completeness Classes in Algebra (you will have to give your UBC CWL; click the Table of Contents tab, and the select "Completeness classes in algebra"). (In general, to access any STOC article from the UBC library go to the STOC Proceedings page in the UBC library, select a year, and then click on the Table of Contents tab; I don't know a better way...) Laurent Hyfil's article in the 1978 STOC proceedings also explains part of the motivation for permanent versus determinant, as discussed in class.
Office Hours Office hours will be given by appointment, as long as this is feasible. When things get too busy, I will give office hours as fixed hours which I will post.
Grading The course grade will be based on a combination of homework problems (50%) and a final project (50%); the meaning of grades in this course will follow the general guildlines for grades for graduate courses in the Mathematics Department.
Homework I will assign homework problems, both from the blog's collection of problems and some additional problems. Here is Homework Set 1; it is based on Chapter 1 and Chapter 3, Section 1. Please hand in at least 3 of the 11 problems by Friday, January 31; and at least 6 of the 11 problems by Friday, February 7. Here is the start of Homework Set 2; it is based on Chapter 2 and related material (formulas and circuits).

UBC Math Home| Joel Friedman Home| Course Materials