We study constraint languages using logical methods.
The aim of the project is to advance the state-of-art of CSP research and improve our understanding of the complexity landscape of constraint languages via enhancement and application of the latest pp-definability-based structural results and techniques, resolving several important open problems.
Constraint satisfaction is a unifying framework and a powerful paradigm for expressing and solving combinatorial tasks from a wide range of real-life applications. Our understanding of the complexity landscape of constraint languages has recently undergone rapid development fuelled by improvements to the structural theory in connection with the resolution of the CSP dichotomy conjecture and the establishment of the algebraic framework for Promise CSP. The fundamental tools are standardized reductions based on primitive positive (pp-) definability and its generalizations, used as means to understand the structure of solution sets.
The project aims to enhance the state-of-art methods based on inspection of the structure of such pp-definability-based reductions and apply them to resolve important open problems in three areas: few subpowers and learnability and evaluability of solution sets, solvability in nondeterministic logspace via Linear Datalog, and progress towards full classification of constraint languages and Promise CSP templates modulo pp-constructibility.
Coming soon.
Coming soon.