The Fields institute and
the Department of Computer Science University of Toronto

CSC 2402H
Methods to deal with intractability

Fall 2009

 

Lecture: Tuesday 15-17, The Fields Institute, Stewart Library

Instructors: Avner Magen and Toniann Pitassi

Office hours: by appointment (SF 2301B, 946-8672).

Tutor: Siavosh Benabbas



Course Outline

The course deals with systematic approaches, based on algebric and geometric reasoning to deal with intractibilitiy (aka NP-hardness). The course will assume very little knowledge about computability and Complexity theory, and still will attempt to deliver toward its later stages advanced concepts and state-of-the-art topics in the relevant theory, including open questions. The course will consist of four parts.

I. Mini-tutorial on complexity theory.

  • Turing Machine and mathematical definition for "efficient computation".
  • Complexity classes P, NP, coNP, NP-completeness, Cook's theorem.
  • Important NP complete problems: SAT, solvability of polynomial identities, integer linear programming, classical graph problems (MaxCut, VertexCover, MaxClique).
  • Randomized complexity classes RP, BPP
  • Hardness of approximation and the PCP theorem.
  • Inapproximability results (wout proofs) of MaxSAT, MaxCut, Vertex Cover, Sparsest Cut. ) Review of state-of-the-art approximation algs and hardness results for these problem
  • Khot's Unique games Conjecture, and implications. Proof Complexity basics
  • What is a propositional Proof system, and how it is connected to P versus NP question How standard algorithms and approximation algorithms fit into the proof complexity framework Important Proof systems that we will consider Resolution, Algebraic proof systems, Matrix Cut Proof systems
  • Overview of lower bounds and algorithmic implications

    II. Using Grobner bases to solve SAT.

  • Proof systems based on Hilbert's Nullstellensatz/Grobner bases.
  • Positive results: Grobner bases algorithms for SAT
  • Negative results: degree and size lower bounds
  • Open problems

    III. (main part of the course) The convex programming approach to approximation algorithms

  • What are linear programs? How do we solve Linear Programs? We will present the simplex, ellipsoid and interior points methods.
  • What are semidefinite programs? solving them using ellipsoid and interior point methods.
  • Proof systems based on linear programming, and semidefinite programming: Lovasz Schrijver, Cutting Planes.
  • Using this toolbox for dealing with NP-hardness. Approximating "basic" problems. MaxCut algorithms and Sparsest cut Algorithms as prime examples. Using Linear and Semi-Definite programs to approximate MaxSAT.
  • The interplay between the analysis of such algorithms with combinatorial/geometrical/ probabilistic notions like concentration-of-measure, isoperimetric inequalities, expanding conditions.
  • Negative results: integrality gaps, LS-based integrality gaps

    IV. Open problems

      

    Grading

    There will be 4 problem sets that will make up the grade for this course.

    Assignments

    assignment 1 (version uploaded Oct 11)
    assignment 2 (version uploaded Oct 31, 4:40PM)
    assignment 3

    Reading

    There is no real text for the course. Here is a list for recommended ones.

  • Approximation Algorithms by Vazirani (2001)
  • Understanding and Using Linear Programming by Matousek and Gartner (2006)
  • Combinatorial Optimization, Algorithms and complexity by Papadimitriou and Steiglitz.
  • Geometric Algorithms and Combinatorial Optimization, by Grotschel, Lovasz and Schrijver (1988)
  • There are also previous lecture notes from courses (within the CS department) that were taught in 2005 and 2007.
  • A good genrel reference for (modern) complexity theory is "Computational Complexity: A Modern Approach" By Arora and Barak. It can be downloaded using this link

    Announcements

    Date Announcement(s)
    30/10

    Assigmnet 2 was uploaded.

    27/10

    Tutorial Thursday 29/10 at 10:00. Location: Bahen 3004. Topics: Duality theorem and ellipsoid algorithm.

    11/10

    typo fixed in A1. Upload again to get the correct version. (A_{ij} = -x_{ji} when i>j and ij an edge. In other words, an entry corresponding to an edge is the negation of its symmetric entry.)

    7/10

    Tutorial tomorrow 8/10 at 10:00. Location: Bahen 3004.

    6/10

    Assigmnet 1 was uploaded.

    22/9

    Class will continue to be held in Stewart library in the Fields (same place as lecture 2).

    9/9

    Welcome to the course's webpage. First class on Monday 14/9, 3-5pm, Fields room 230.