Fall 2016

Power and Limits of LP and SDP Relaxations

Wednesday, November 9th, 2016 2:00 pm2:30 pm

Add to Calendar

We will discuss precise characterisations of the power of convex relaxations for constraint satisfaction problems (CSPs). In particular, we will present characterisations of general-valued CSPs that can be solved optimally using the Basic LP relaxation, the Sherali-Adams LP relaxation, and the Lasserre SDP relaxation. These characterisations, in terms of certain algebraic objects known as fractional polymorphisms, have been instrumental in obtaining several complexity classifications for CSPs. Based on joint work with J. Thapper.