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
    assignment 4 (Note: the current revision has a small update in question 3a). Please email your electronic ex4 to siavosh (siavosh@cs) and if you write your work by hand, please leave your papers with Elizabeth Ribeiro, SF 2301D by the due date.)

    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

    some references

    Algebraic Proof Systems

  • Using the Grobner Basis Algorithm to find Proofs of Unsatisfiability (Clegg, Edmonds Impagliazzo)
  • Algebraic Propositional Proof Systems (Survey article) Pitassi
  • (First article on Nullstellensatz Proof system) Beame, Impagliazzo, Krajicek, Pitassi, Pudlak Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
  • (Lower bounds for Nullsatz refutation of Induction) Buss, Pitassi. Good Degree Bounds on Nullstellensatz Refutations of the Induction Principle
  • (Paper using Nullsatz to solve Graph colorability) DeLoaea, Lee, Malkin, Margulis Hilbert's Nullstellensatz and and Algorithm for Proving Combinatorial Infeasibility
  • (Linear lower bounds for PC refutations of the PHP) Razborov. Lower Bounds for the Polynomial Calculus
  • (More lower bounds for PC refutations of PHP) Alekhnovich and Razborov.

    Announcements

    Date Announcement(s)
    29/11

    Please email your electronic ex4 to siavosh (siavosh@cs) and if you write your work by hand, please leave your papers with Elizabeth Ribeiro, SF 2301D by the due date.

    29/11

    Assigmnet 4 was uploaded.

    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.