Maximilian Hadek

Maximilian Hadek, Tomáš Jakl, Jakub Opršal

The so-called algebraic approach to the constraint satisfaction problem (CSP) has been a prevalent method of the study of complexity of these problems since early 2000's. The core of this approach is the notion of polymorphisms which determine the complexity of the problem (up to log-space reductions). In the past few years, a new, more general version of the CSP emerged, the promise constraint satisfaction problem (PCSP), and the notion of polymorphisms and most of the core theses of the algebraic approach were generalised to the promise setting. Nevertheless, recent work also suggests that insights from other fields are immensely useful in the study of PCSPs including algebraic topology. In this paper, we provide an entry point for category-theorists into the study of complexity of CSPs and PCSPs. We show that many standard CSP notions have clear and well-known categorical counterparts. For example, the algebraic structure of polymorphisms can be described as a set-functor defined as a right Kan extension. We provide purely categorical proofs of core results of the algebraic approach including a proof that the complexity only depends on the polymorphisms. Our new proofs are substantially shorter and, from the categorical perspective, cleaner than previous proofs of the same results. Moreover, as expected, they are applicable more widely. We believe that, in particular in the case of PCSPs, category theory brings insights that can help solve some of the current challenges of the field.

Libor Barto, Maximilian Hadek, Dmitriy Zhuk

We develop a unified framework to characterize the power of higher-level algorithms for the constraint satisfaction problem (CSP), such as $k$-consistency, the Sherali-Adams LP hierarchy, and the affine IP hierarchy. As a result, solvability of a fixed-template CSP or, more generally, a Promise CSP by a given level is shown to depend only on the polymorphism minion of the template. Similarly, we obtain a minion-theoretic description of $k$-consistency reductions between Promise CSPs. We introduce a new hierarchy of SDP-like vector relaxations with vectors over $\mathbb Z_{p}$ in which orthogonality is imposed on $k$-tuples of vectors. Surprisingly, this relaxation turns out to be equivalent to the $k$-th level of the AIP-$\mathbb{Z}_p$ relaxation. We show that it solves the CSP of the dihedral group $\mathbf{D}_4$, the smallest CSP that fools the singleton BLP+AIP algorithm. Using this vector representation, we further show that the $p$-th level of the $\mathbb{Z}_p$ relaxation solves linear equations modulo $p^2$.