Vi studerar integrality luckor för SDP lättnader av begränsningar tillfredsställelse problem, i hierarkin av SDPs definieras av Lasserre. Schoenebeck [23] nyligen visade de första integratitet luckor för dessa problem, visar att för MAX k-XOR, förhållandet mellan SDP optimal till heltal optimal kan vara så stor som 2 även efter  och n) rundor i Lasserre hierarkin. Vi visar att för den allmänna MAX k-CSP problem, detta förhållande kan vara så stor som 2 k /2k - när alfabetet är binär och q k /q(q − 1)k - när alfabetet storlek en prime q, även efter  och n) rundor i Lasserre hierarkin. Vi utforskar också hur man kan översätta luckor för CSP till integrality luckor för andra problem med hjälp av minskningar, och etablera SDP luckor för maximal oberoende uppsättning, Ungefärliga diagramfärgning, kromatiskt tal och minsta Vertex Cover. För Independent Set och Chromatic Number, visar vi integrality luckor i n/2
Via minskningar från detta resultat, Tulsiani visade gap instanser för Max k-CSP (för  och (n) rundor), och fall med n 1‐o(1) gap för  och 2 ε log n rundor för oberoende uppsättning och kromatiska nummer REF.
CSP gaps and reductions in the lasserre hierarchy
{'venue': "STOC '09", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}