We show that approximate graph colouring is not solved by constantly many levels of the lift-
and-project hierarchy for the combined basic linear programming and affine integer …

We propose a new algorithm for Promise Constraint Satisfaction Problems (PCSPs). It is a
combination of the Constraint Basic LP relaxation and the Affine IP relaxation (CLAP). We …

For a constraint satisfaction problem (CSP), a robust satisfaction algorithm is one that
outputs an assignment satisfying most of the constraints on instances that are near …

We study the power of the bounded-width consistency algorithm in the context of the fixed-
template Promise Constraint Satisfaction Problem (PCSP). Our main technical finding is that …

We show that approximate graph colouring is not solved by any level of the affine integer
programming (AIP) hierarchy. To establish the result, we translate the problem of exhibiting …

We provide a unified framework to study hierarchies of relaxations for Constraint Satisfaction
Problems and their Promise variant. The idea is to split the description of a hierarchy into an …

The study of the complexity of the constraint satisfaction problem (CSP), centred around the
Feder-Vardi Dichotomy Conjecture, has been very prominent in the last two decades. After a …

A classic result due to Schaefer Proceedings of STOC 78, ACM, 1978, pp. 216--226
classifies all constraint satisfaction problems (CSPs) over the Boolean domain as being …

We give a complete complexity classification for the problem of finding a solution to a given
system of equations over a fixed finite monoid, given that a solution over a more restricted …

The 1-in-3 and Not-All-Eqal satisfiability problems for Boolean CNF formulas are two well-
known NP-hard problems. In contrast, the promise 1-in-3 vs. Not-All-Eqal problem can be …