2 citations · 2 across the 4 of their papers we have counts for
4 papers
Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard
Leonid Dorochko, Michał 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…
Model-checking positive equality free logic on a fixed structure (direttissima)
Manuel Bodirsky, Marcin Kozik, Florent Madelaine +2
We give a new, direct proof of the tetrachotomy classification for the model-checking problem of positive equality-free logic parameterised by the model. The four complexity classe…
Quasi Directed Jonsson Operations Imply Bounded Width (For fo-expansions of symmetric binary cores with free amalgamation)
Michal Wrona
Every CSP(B) for a finite structure B is either in P or it is NP-complete but the proofs of the finite-domain CSP dichotomy by Andrei Bulatov and Dimitryi Zhuk not only show the co…
The complete classification for quantified equality constraints
Dmitriy Zhuk, Barnaby Martin, Michal Wrona
We prove that QCSP is PSpace-complete, settling a question open for more than ten years. This completes the complexity classification for the QCSP…