
Math 523201 Page, Spring 2014
This course gives a selfcontained
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:
 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):
 Turing Machines (1.1, 1.2),
 Uncomputability (1.5),
 P (1.6) and NP (2.1),
 Cook's Theorem (2.3) and NPcomplete problems (2.4, perhaps 2.2),
 Algebraic complexity (16.1),
 Randomized complexity (7.17.3).

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):
 Application (before we give the theory):
Two person zero sum games (11.111.3),
 Linear programs (1.2) and the simplex method (2.12.4) and
the perturbation method (3.3),
 Duality (5.15.4) and complementary slackness (5.5),
 Application: Yao's Theorem on Randomized Computation (Arora and Barak, 12.4.1).

Advanced topics, to be chosen from (based, in part, on a student poll):

The "Permanent versus Determinant" question
(Arora and Barak, 16.1), as an algebraic analogue of P versus NP;
 Other interesting questions/bounds in complexity theory;
 Other applications in linear programmig;
 A quadratic lower bound for the "Permanent versus Determinant" question;
 An introduction to the MulmuleySohoni 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 MulmuleySohoni'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).

