3 papers
cs.LO2026
When Darwin met Ianus: dichotomies of expressivity
Johanna Brunar, Michael Pinsker, Moritz Schöbi
The classifications of temporal and phylogeny constraint languages stand among the most seminal complexity classifications within infinite-domain Constraint Satisfaction Problems (…
math.LO2026
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…
math.LO2025
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.