On the limits of Linear and Affine Integer Programming relaxations for Constraint Satisfaction Problems

A Constraint Satisfaction Problem (CSP) asks whether values from a specified domain can be assigned to given variables subject to a set of constraints. The Promise Constraint Satisfaction Problem (PCSP) is a variant of the CSP in which the input is a pair of similar CSP instances, and the question is whether the stronger instance can be satisfied, or even the weaker one is unsatisfiable. Algorithms for the CSP and PCSP have been a major research direction for several decades. While the complexity of the CSP is largely understood, that of the PCSP is widely open. One of the recent algorithmic approaches to both problems uses various combinations of Linear and Affine Programming relaxations of the problems. It has even been proposed that such a combination may serve as a universal efficient for all cases of tractable CSPs and PCSPs. In this thesis we refute this conjecture for some combinations of local algorithms, Linear, and Affine Integer Programming relaxations.