research
∙
02/23/2023
Symmetries of structures that fail to interpret something finite
We investigate structural implications arising from the condition that a...
share
research
∙
05/10/2022
Weisfeiler-Leman Invariant Promise Valued CSPs
In a recent line of work, Butti and Dalmau have shown that a fixed-templ...
research
∙
05/10/2022
Fixed-Template Promise Model Checking Problems
The fixed-template constraint satisfaction problem (CSP) can be seen as ...
research
∙
07/20/2021
Combinatorial Gap Theorem and Reductions between Promise CSPs
A value of a CSP instance is typically defined as a fraction of constrai...
research
∙
04/23/2021
Minimal Taylor Algebras as a Common Framework for the Three Algebraic Approaches to the CSP
This paper focuses on the algebraic theory underlying the study of the c...
research
∙
10/10/2020
Constraint Satisfaction Problems over Finite Structures
We initiate a systematic study of the computational complexity of the Co...
research
∙
10/09/2020
Symmetric Promise Constraint Satisfaction Problems: Beyond the Boolean Case
The Promise Constraint Satisfaction Problem (PCSP) is a recently introdu...
research
∙
10/09/2020
Finitely Tractable Promise Constraint Satisfaction Problems
The Promise Constraint Satisfaction Problem (PCSP) is a generalization o...
research
∙
05/01/2020
Sensitive instances of the Constraint Satisfaction Problem
We investigate the impact of modifying the constraining relations of a C...
research
∙
09/12/2019
Topology is irrelevant (in a dichotomy conjecture for infinite domain constraint satisfaction problems)
The tractability conjecture for finite domain Constraint Satisfaction Pr...
research
∙
09/11/2019
Promises Make Finite (Constraint Satisfaction) Problems Infinitary
The fixed template Promise Constraint Satisfaction Problem (PCSP) is a r...
research
∙
09/11/2019