Math 523-201 Page, Spring 2014
This course gives a self-contained introduction to combinatorial optimization. We do not assume a background in computer science theory, although we assume mathematical sophistication on the graduate math level.
Roughly speaking the class will consist of a month of each of the following topics (1) linear programming and applications, (2) computability and P versus NP, (3) current approaches to P versus NP and related problems.
Our course will use parts of two texts: Algorithms, by Dasgupta, Papadimitriou, and Vazirani and Computational Complexity, by Arora and Barak(click on the word "Book" in the middle of the page; you may have to enter some sort of UBC identification). Both texts are currently available online (the latter is via Books24x7, which will require your UBC CWL login). You can also purchase hard copies via online bookstores.
The third topic is like to cover part of the Mulmuley-Sohoni approach to P versus NP; we may use these notes of mine. I will not assume a background in algebraic geometry, but if you want to pursue this approach beyond this course, that would help.