Personal tools
You are here: Home Events LFCS seminar: Standa Zivny: Power and limits of convex relaxations

LFCS seminar: Standa Zivny: Power and limits of convex relaxations

— filed under: ,

What
  • LFCS Seminar
  • Upcoming events
When Mar 06, 2017
from 04:00 PM to 05:00 PM
Add event to calendar vCal
iCal


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.

Document Actions