Abstracts
(sorted by first name)
PCSP Algorithms: Rounding and Meta-Problems
Alberto Larrauri
Recently, it has been shown that three of the main PCSP algorithms, BLP, AIP and BLP+AIP, are hard to round and have undecidable meta-problems. In this talk we introduce these results, we outline the proof strategy going over some recent improvements, and we discuss open questions.
https://doi.org/10.48550/arXiv.2504.04639
On Approximability of Satisfiable CSPs & Applications
Amey Bhangale
The satisfiability problem for Constraint Satisfaction Problems (CSPs) asks whether a CSP instance admits an assignment that satisfies all constraints. For a $k$-ary predicate $P:[q]^k \to {0,1}$, where $P(x)=1$ iff $x$ satisfies the constraint, the problem CSP(P) consists of constraints obtained by applying P to ordered $k$-tuples of variables. By the Dichotomy Theorem of Bulatov and Zhuk, this problem is either in P or NP-complete.
A natural question is to determine the threshold $\alpha(P) < 1$ for each NP-complete CSP(P) such that
(i) there is a polynomial-time algorithm that finds an assignment satisfying an $\alpha(P)$ fraction of constraints on satisfiable instances, and
(ii) for every $\epsilon>0$, finding an assignment satisfying an $(\alpha(P)+\epsilon)$ fraction is NP-hard.
While such thresholds are known for some predicates (e.g., $7/8$ for 3SAT by Håstad), determining $\alpha(P)$ in general remains widely open.
This talk presents recent work initiating a systematic study of this question, including new analytical theorems and a proposed approximation algorithm. I will also discuss applications to additive combinatorics, including improved bounds for sets avoiding restricted 3-term arithmetic progressions and results related to the density Hales–Jewett theorem in $[3]^n$.
The talk will be based on joint works with Subhash Khot, Yang P. Liu, and Dor Minzer.
Satisfiability of commutative vs. non-commutative CSPs
Andrei Bulatov
The Mermin-Peres magic square is a celebrated example of a system of Boolean
linear equations that is not (classically) satisfiable but is satisfiable via
linear operators on a Hilbert space of dimension four. A natural question is
then, for what kind of problems such a phenomenon occurs? Atserias, Kolaitis,
and Severini answered this question for all Boolean Constraint Satisfaction
Problems (CSPs): For 0-Valid-SAT, 1-Valid-SAT, 2-SAT, Horn-SAT, and Dual
Horn-SAT, classical satisfiability and operator satisfiability is the same and
thus there is no gap; for all other Boolean CSPs, these notions differ as there
are gaps, i.e., there are unsatisfiable instances that are satisfiable via
operators on Hilbert spaces.
We generalize their result to CSPs on arbitrary finite domains and give an
almost complete classification: First, we show that NP-hard CSPs admit a
separation between classical satisfiability and satisfiability via operators on
finite- and infinite-dimensional Hilbert spaces. Second, we show that tractable
CSPs of bounded width have no satisfiability gaps of any kind. Finally, we show
that tractable CSPs of unbounded width can simulate, in a
satisfiability-gap-preserving fashion, linear equations over an Abelian group of
prime order p; for such CSPs, we obtain a separation of classical satisfiability
and satisfiability via operators on infinite-dimensional Hilbert spaces.
Furthermore, if p=2, such CSPs also have gaps separating classical
satisfiability and satisfiability via operators on finite- and
infinite-dimensional Hilbert spaces.
https://doi.org/10.48550/arXiv.2404.11709
Promise compactness and promise CSPs
Bertalan Bodor
Let $(\mathfrak{A},\mathfrak{B})$ be a promise template, i.e., a pair of structures such that $\mathfrak{A}$ homomorphically maps to $\mathfrak{B}$. Then we denote by $K_{(\mathfrak{A},\mathfrak{B})}$ the following statement.
For every structure $\mathfrak{I}$ with the same signature as $\mathfrak{A}$, if all finite substructures of $\mathfrak{I}$ homomorphically map to $\mathfrak{A}$ then $\mathfrak{I}$ homomorphically maps to $\mathfrak{B}$.
In my talk I will examine the strengths of different compactness principles $K_{(\mathfrak{A},\mathfrak{B})}$ over ZF. We know for example that if $(\mathfrak{A},\mathfrak{B})$ pp-constructs $(\mathfrak{C},\mathfrak{D})$ then $K_{(\mathfrak{A},\mathfrak{B})}$ implies $K_{(\mathfrak{C},\mathfrak{D})}$. This observation suggests that the harder the PCSP over $(\mathfrak{A},\mathfrak{B})$ is, the stronger the compactness principle $K_{(\mathfrak{A},\mathfrak{B})}$ is. In particular, we know that if $(\mathfrak{A},\mathfrak{B})$ pp-constructs EVERYTHING then $K_{(\mathfrak{A},\mathfrak{B})}$ is equivalent to the ultrafilter lemma. In my talk I will talk about how this statement can be generalized to some others promise templates which are known to have hard PCSPs, for example I will show that $K_{(K_3,K_5)}$ is also equivalent to the ultrafilter lemma. The proof is largely based on a reduction involving a generalized version of minion homomorphisms (called $(d,r)$-minion homomorphisms) introduced by Barto and Kozik.
Everything is a cheese (From infinite CSPs to finite PCSPs)
Christoph Spiess
The complexity of finite-domain Constraint Satisfaction Problems (CSPs) was classified in 2017 by the dichotomy theorem of Bulatov and Zhuk. Two natural extensions are infinite-domain CSPs and finite-domain Promise CSPs (PCSPs), both of which significantly generalize the finite-domain setting.
The Bodirsky-Pinsker dichotomy conjecture proposes a dichotomy for certain well-behaved infinite CSP templates. We show that every non-trivially tractable template within its scope yields a finite-domain PCSP that is not finitely tractable. More precisely, up to Datalog reductions, each such template serves as a tractability witness, via the sandwich method, for a finite-domain PCSP that admits no finite witness of this form. This generalizes a recent result of Mottet and strengthens the novel connection between the Bodirsky-Pinsker conjecture and finite-domain PCSPs.
https://doi.org/10.4230/LIPIcs.MFCS.2025.83
Analytical approach to Boolean PCSPs
Demian Banakh
In a joint work with Katzper Michno, we develop an analytical framework for Boolean Promise Constraint Satisfaction Problems (PCSPs) that studies polymorphisms through the notion of influence from Fourier analysis of Boolean functions. Extending the work of Brakensiek, Guruswami, and Sandeep [ICALP'21] on Ordered PCSPs, we identify two general phenomena in Boolean minions indicative of hardness or tractability: (1) preservation of coordinate influence under random 2-to-1 minors and (2) the presence of sharp thresholds. We demonstrate that these phenomena occur in broader settings than previously established, yielding new hardness/tractability results for minions consisting of unate or polynomial threshold functions.
How to find a symmetric object in an ugly minion
Dmitriy Zhuk
Most natural universal algorithms for the CSP can be characterized by a minion: the algorithm answers "Yes" on a CSP instance if and only if the corresponding label cover instance has a relaxed solution in the minion. Unfortunately, these minions are often unwieldy, and it can be difficult to write down a single nontrivial identity satisfied by any of their objects. As a result, the minion characterization does not directly help to check whether the algorithm solves $\mathrm{PCSP}(\mathbb A,\mathbb B)$.
Nevertheless, mapping such a minion into a locally finite one forces many objects
to be identified, and these identifications can give rise to objects satisfying
non-trivial symmetry identities. Since $\mathrm{Pol}(\mathbb{A}, \mathbb{B})$ is
locally finite whenever $\mathbb{A}$ and $\mathbb{B}$ are finite, this observation
has concrete consequences for the complexity of $\mathrm{PCSP}(\mathbb A,\mathbb B)$: if the resulting identities are strong enough to round an approximate solution, one
obtains a better characterization of when the algorithm solves $\mathrm{PCSP}(\mathbb A,\mathbb B)$.
We explain how this idea works for the singleton arc-consistency algorithm,
deriving that the singleton and constraint-singleton variants have the same power
for finite relational structures, and are both characterized by palette symmetric
polymorphisms. We also present a concrete temporal CSP template showing that
this equivalence fails for infinite structures.
https://arxiv.org/abs/2509.18434
On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems
Neng Huang
In the Minimum Cost Constraint Satisfaction Problem (MinCostCSP), we are given a CSP instance together with costs for assigning labels to variables, and the goal is to find a satisfying assignment which minimizes the total cost. In this talk, I will survey some known results on this problem, and then present our recent work on its constant-factor approximability. We give a $|D|$-approximation algorithm for any constraint language that has the dual discriminator operator as a polymorphism, where $D$ is the domain. On the hardness side, we show that any constraint language that admits a constant-factor approximation must have a near-unanimity polymorphism unless P = NP. For constraint languages containing all permutation relations, this yields a dichotomy between $|D|$-approximability and inapproximability within every constant factor. Finally, we show that having a majority polymorphism is in general not sufficient for constant-factor approximability, assuming the Unique Games Conjecture.
Based on joint work with Ian DeHaan and Euiwoong Lee.
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2025.19
The Polynomial Hierarchy and ω-categorical CSPs
Jakub Rydval
In 2008, Bodirsky and Grohe showed that for every level of the Polynomial Hierarchy (PH) above coNP there are ω-categorical CSPs complete for this level. We show that, in fact, there are ω-categorical CSPs complete for any level of the PH. To this end, we use a recent result of Bodirsky, Knäuer, and Rudolph for constructing ω-categorical CSPs from sentences of Monadic Second-Order logic (MSO) with certain preservation properties. As a secondary contribution, we develop a new tool for producing MSO sentences satisfying said preservation properties. In the present talk, I give an overview of the above-mentioned results and motivate several new questions.
This is joint work with Santiago Guzmán-Pro.
Toward The Algorithm
Libor Barto
I will present work in progress aimed at designing a polynomial‑time algorithm for constraint problems. The algorithm should be natural (free of ad hoc tricks), uniform (with running time depending only polynomially on domain sizes), and powerful (able to correctly decide at least all instances of any tractable fixed‑template finite‑domain CSP).
The complexity of quantum constraint satisfaction
Lorenzo Ciardo
The quantum CSP is a non-classical version of the standard CSP, motivated by questions in quantum physics, particularly the role of entanglement in information-processing tasks. After a brief introduction to the area, I will present an algebraic framework for reductions between quantum CSPs based on the notion of quantum polymorphisms. This framework gives a characterisation of the classical algebraic CSP reductions that lift to the quantum setting, via commutativity gadgets introduced by Ji, and hence provides a systematic way to apply the algebraic CSP machinery to obtain complexity statements about quantum CSPs. Applications include the complexity classification of the quantum CSPs parameterised by odd cycles, the Siggers digraph, and all Boolean structures. The starting points of these reductions are quantum XOR (shown undecidable by Slofstra) or quantum 3SAT (shown undecidable as a consequence of the MIP$^*$=RE theorem).
This talk is based on joint work with Gideo Joubert and Antoine Mottet.
https://doi.org/10.48550/arXiv.2511.23445
FPT-approximation of MinCSPs: A progress report
Magnus Wahlström
The following is a very natural question in need of a dichotomy theorem:
Let L be a finite, finite-domain constraint language. In MinCSP(L), the input is an instance of CSP(L) and a parameter k, and we want to know if there is an assignment that satisfies all but at most k constraints of the input.
For which languages L does this problem has a constant-factor FPT approximation parameterized by k?
This question depends only on the universal algebraic properties of L (i.e. up to a minor assumption it is preserved by pp-constructions) and so should be feasible to characterize.
I will review what we know so far about this question (and the related question of exact FPT-algorithms) beyond the Boolean domain.
Hierarchies galore
Max Hadek
We develop a uniform framework to characterize the power of higher-level algorithms for the constraint satisfaction problem, 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.
Minimal Mal'cev clones
Michael Kompatscher
In the search for a uniform algorithm solving all finite tractable CSPs, several promising candidates were dismissed because of group counterexamples. Thus, it already seems to be a major challenge to find a uniform algorithm that works for all Mal'cev CSPs. In order to reach this goal, it might be fruitful to only consider maximal such CSPs, i.e. CSP(A), for which the polymorphism clone Pol(A) is a minimal Mal'cev clone (with respect to inclusion).
In this talk, I would like to discuss some general properties of minimal Mal'cev clones (including an unpublished result by Z. Brady that minimal Mal'cev implies minimal Taylor), and discuss an open conjecture in the nilpotent case.
https://doi.org/10.1007/s00025-025-02568-2
Decidability of interpretability
Michael Pinsker
The Bodirsky-Pinsker conjecture asserts a P vs. NP-complete dichotomy for the computational complexity of CSPs of first-order reducts of finitely bounded homogeneous structures. Prominently, two structures in the scope of the conjecture have log-space equivalent CSPs if they are pp-bi-interpretable, or equivalently, if their polymorphism clones are topologically isomorphic. The latter gives rise to the algebraic approach which regards structures with topologically isomorphic polymorphism clones as equivalent and seeks to identify structural reasons for hardness or tractability in topological clones. We establish that the equivalence relation of pp-bi-interpretability underlying this approach is reasonable: On the one hand, we show that it is decidable under mild conditions on the templates; this improves a theorem of Bodirsky, Pinsker and Tsankov (LICS'11) on decidability of equality of polymorphism clones. On the other hand, we show that within the much larger class of transitive $\omega$-categorical structures without algebraicity, the equivalence relation is of lowest possible complexity in terms of descriptive set theory: namely, it is smooth, i.e., Borel-reduces to equality on the real numbers.
On our way to showing the first result, we establish that the model-complete core of a structure that has a finitely bounded Ramsey expansion (which might include all structures of the Bodirsky-Pinsker conjecture) is computable, thereby providing a constructive alternative to previous non-constructive proofs of its existence.
This is joint work with Roman Feller (TU Wien).
https://doi.org/10.48550/arXiv.2602.02302
Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard
Michal Wrona
Feder-Vardi conjecture, which proposed that every finite-domain Constraint Satisfaction Problem (CSP) is either in P or it is NP-complete, has been solved independently by Bulatov and Zhuk almost ten years ago. Bodirsky-Pinsker conjecture which states a similar dichotomy for countably infinite first-order reducts of finitely bounded homogeneous structures is wide open.
In this paper, we prove that CSPs over first-order expansions of finitely bounded homogeneous model-complete cores are either first-order definable (and hence in non-uniform AC0) or L-hard under first-order reduction. It is arguably the most general complexity dichotomy when it comes to the scope of structures within Bodirsky-Pinsker conjecture. Our strategy is that we first give a new proof of Larose-Tesson theorem, which provides a similar dichotomy over finite structures, and then generalize that new proof to infinite structures.
It is joint work Leonid Dorochko
https://arxiv.org/abs/2601.22691
Troublemakers in the infinite: directed graph colouring in temporal and phylogeny constraint languages
Moritz Albert Schöbi
In the early stages of the systematic research programme on CSPs, those induced by finite graphs were among the first to be studied. Hell and Nešetřil showed already in 1990 that every finite undirected non-bipartite graph either gives rise to an NP-complete CSP, or has a loop (in which case its CSP trivial). This result was later extended to finite directed graphs. When it comes to infinity, the graphs 'closest to finite' are the ones whose factor by their automorphism group is finite. While the Hell-Nešetřil theorem for undirected graphs has been successfully generalised to this framework, the directed case poses significant challenges. By solving it for digraphs pp-interpretable in temporal or phylogeny constraint languages – which stand among the algorithmically most mysterious ones within the completely classified infinite-domain CSPs – hope is sparked that the finite digraph dichotomy may be fully liftable to the infinite. Based on joint work with Johanna Brunar and Michael Pinsker.
https://doi.org/10.48550/arXiv.2509.04347
Towards infinite PCSP: a dichotomy for monochromatic cliques
Tamio-Vesa Nakajima
We discuss a promise extension of MMSNP, and a dichotomy for a fragment of this problem: given a graph G that admits a c-colouring without any monochromatic k-clique, find a d-colouring without any monochromatic l-clique. The dichotomy is conditional on the Rich 2-to-1 conjecture, and extends recent work of Braverman, Khot, Lifshitz and Minzer. The techniques used also lead to progress on some other PCSPs, for example new conditional hardness results for LO colouring.
This is joint work with Demian Banakh and Alexey Barsukov
The rabbit hole of adjunctions
Tomas Jakl
In this talk I will survey a categorical perspective on the algebraic approach to the (P)CSP. In particular we discuss how many of standard constructions in the CSP world can be equivalently described as well-known and well-studied categorical notions, such as Kan extensions, Grothendieck construction, nerve-realisation (akin to the constructions in algebraic topology), etc. Time permitting, we will show how some of the fundamental theorems, such as the characterisation of gadget reductions as minion morphisms, follow from elementary properties of the corresponding categorical constructions.
https://arxiv.org/abs/2503.10353
Redundancy is all you need (for CSP sparsification)
Venkatesan Guruswami
Constraint Satisfaction Problems (CSPs) form a broad and central class in the theory of computation. I will describe a result (with J. Brakensiek, STOC ’25) showing that every CSP admits a sparsifier whose size is within polylogarithmic factors of its maximum non-redundant instance, while preserving the value of every assignment up to a small multiplicative error. A non-redundant instance is one where every constraint is essential, in the sense that some assignment satisfies exactly that constraint and no others—making such instances natural lower bounds for sparsification (for example, spanning trees are the non-redundant cut instances in graphs).
Our result is established in the general setting of set families, yielding a VC-type theorem for multiplicative approximation. This unifies and extends known sparsification results for graph cuts, linear codes, and broad CSP classes. The proof hinges on an elegant entropic inequality underlying Gilmer's recent breakthrough on the union-closed sets conjecture.
As a consequence of our main theorem, several results from the non-redundancy (NRD) literature immediately extend to CSP sparsification. Time permitting, we will mention some results, including from follow-up works, that illuminate the rich landscape of NRD itself.
https://dl.acm.org/doi/10.1145/3717823.3718212
The Richness of CSP Non-redundancy
Victor Lagerkvist
The non-redundancy of an n-variable CSP(P) instance (NRD(P,n)) is the maximum number of constraints possible without introducing redundancy, i.e., a constraint being implied by a set of other constraints. This parameter has a long tradition in logic and classical, symbolic AI but has recently been shown to also have strong ties to sparsifiability of CSP(P). Importantly, the NRD parameter can be studied with universal algebra, and in this talk I will go through the basics of this approach, detail how it connects to (partial) promise polymorphisms, as well as some concrete applications.
https://arxiv.org/abs/2507.07942
A Preservation Theorem for Valued Structures
Žaneta Semanišinová
The algebraic approach to constraint satisfaction problems (CSPs) has been very fruitful for classifying computational complexity. This approach is based on the interplay of polymorphisms of the template and of relations that are primitively positively definable in the template. A central result in the area is the so-called preservation theorem, due to Bodirsky and Nešetřil for templates with an oligomorphic automorphism group, which states that a relation is primitively positively definable in a relational structure $\mathfrak{A}$ if and only if it is preserved by all polymorphisms of $\mathfrak{A}$.
Valued CSPs are a natural generalization of CSPs that allows to model optimization problems by replacing relations in the template by cost functions. For valued CSPs over finite-domain templates a preservation theorem was proved by Fulla and Živný, using the more general concepts of fractional polymorphisms and expressibility instead of polymorphisms and primitive positive definability. The focus of this talk is an ongoing project towards a common generalization of the result of Bodirsky and Nešetřil and of Fulla and Živný for valued CSPs over infinite-domain templates. We conjecture that given a valued structure $\Gamma$ with an oligomorphic automorphism group, a valued relation $R$ is expressible in $\Gamma$ if and only if $R$ is improved by all fractional polymorphisms of $\Gamma$. If true, this result would have far-reaching consequences related to the complexity of valued CSPs and to the algebraic structure of templates for valued CSPs, e.g., existence of cores.
This is joint work with Antoine Mottet.