The Bodirsky-Pinsker conjecture is an infinite counterpart to the Feder-Vardi dichotomy conjecture for Constraint Satisfaction Problems (CSPs) with finite templates. While the latter has been confirmed independently by Bulatov and Zhuk, the former remains wide open. In this talk, we shed light on three meta-problems regarding the scope of this conjecture.
Our first result provides a significant structural simplification of this scope: we prove that the conjecture is equivalent to its restriction to templates without algebraicity, a crucial assumption in many powerful classification methods. The second result provides a simplification of algebraic nature: any algebraic condition characterizing any complexity class within the conjecture must be satisfiable by injections. In particular, this offers insight into which universal-algebraic conditions for the complexity of finite-template CSPs may be successfully lifted to the infinite case. The third result we are going to explore links the conjecture to so-called Promise Constraint Satisfaction Problems (PCSPs): using the construction from the first result, virtually every structure from the scope of the conjecture allows us to construct a sandwich structure for a non-finitely tractable finite-domain PCSP.
This is joint work with Michael Pinsker, Jakub Rydval and Christoph Spiess.
Eliminating algebraicity and enforcing injectivity in infinite-domain constraint satisfaction
We will show how to use root systems of types E6, E7, and E8 to construct generalizations of quantum Pfaffians and quantum Hafnians. These constructions are closely related to the combinatorics of del Pezzo surfaces, and they give rise to new q-analogues of an invariant cubic polynomial in type E6,and a quartic polynomial in type E7.
This is work in progress with Tianyuan Xu (University of Richmond).
Generalized quantum Pfaffians and quantum Hafnians
Eliminating algebraicity and enforcing injectivity in infinite-domain constraint satisfaction