4 papers
Deciding Amalgamation Beyond Arity Two: The Semantic Horn Case
Jakub Rydval
We study the amalgamation decision problem: given a universal first-order sentence , decide whether the class of its finite models has the amalgamation property…
The Polynomial Hierarchy and -categorical CSPs
Santiago Guzmán Pro, Jakub Rydval
In 2008, Bodirsky and Grohe showed that for every -level of the Polynomial Hierarchy (PH) there are -categorical Constraint Satisfaction Problems (CSPs) comple…
The random ordered graph is a semi-retract of the canonically ordered atomless Boolean algebra
Michael Pinsker, Jakub Rydval, Moritz Schöbi +1
We prove that the random ordered graph is a semi-retract of the canonically ordered atomless Boolean algebra, hereby answering an open question of Bartošová and Scow.
Three Fundamental Questions in Modern Infinite-Domain Constraint Satisfaction
Michael Pinsker, Jakub Rydval, Moritz Schöbi +2
The Feder-Vardi dichotomy conjecture for Constraint Satisfaction Problems (CSPs) with finite templates, confirmed independently by Bulatov and Zhuk, has an extension to certain wel…