6 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…
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…
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) comp…
The Golden Path to Guarded Monotone Strict NP
Alexey Barsukov, Michael Pinsker, Jakub Rydval
Guarded Monotone Strict NP (GMSNP) extends Monotone Monadic Strict NP (MMSNP) by guarded existentially quantified predicates of arbitrary arities. We prove that the containment and…
Finitely Bounded Homogeneity Turned Inside-Out
Jakub Rydval
Deciding the amalgamation property for a given class of finite structures is an important subroutine in classifying countable finitely homogeneous structures. We study the computat…
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.