# 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.