skip to content

On the power of Lovasz-Schrijver hierarchy

Thursday 13th April 2006 - 14:30 to 15:30
INI Seminar Room 1

Lov\'{a}sz and Schrijver described a generic method of tightening the LP and SDP relaxation for any $0$-$1$ optimization problem. These tightened relaxations were the basis of several celebrated approximation algorithms (such as for MAX-CUT, MAX-3SAT, and SPARSEST CUT).

In this talk I will survey recent lower bounds for the number of rounds in this model for well-known problems such as MAX-SAT, Hypergraph Vertex Cover and Minimum Set Cover. Also I will elaborate why these lower bounds are encoding dependent, in particular the standard NP reductions do not seem to work in this model. This fact leads to the wide list of open problems, which appear important for proof complexity, computational complexity and algorithm design.

University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons