Title: Performance of Lovasz-Schrijver Lift-and-Project Methods on 0,1 Integer Programming Problems

I will first review two procedures to solve combinatorial optimization problems, due to Lov�sz and Schrijver. One of the procedures is based on polyhedral relaxations, while the other is defined using the cone of symmetric positive semidefinite matrices. When applied to the stable set problem, one step of the procedures generate convex relaxations of the underlying 0,1 solution set with very nice properties. In the case of the relaxation using the cone of positive semidefinite matrices, the convex relaxation generated by the method is tighter than the polytope given by all the clique inequalities of the underlying graph. Secondly, I will illustrate the limitations of the Lov�sz-Schrijver procedure with the positive semidefiniteness constraint by completely characterizing its worst-case behavior on the matching problem (joint work with T. Stephen). Finally, I will answer the question ``when does the positive semidefiniteness constraint help in such Lift-and-Project Methods ?'' (joint work with M. X. Goemans).