<div class="csl-bib-body">
<div class="csl-entry">Schöbi, M. A. (2025, September 7). <i>Algebraicity is irrelevant (in the dichotomy conjecture for infinite-domain constraint satisfaction problems)</i> [Conference Presentation]. Summer School on General Algebra and Ordered Sets (SSAOS 2025), Blansko, Czechia. http://hdl.handle.net/20.500.12708/225146</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/225146
-
dc.description.abstract
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 two meta-problems regarding the scope of this conjecture. Our first
result provides a significant structural simplification: 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. This is joint work with Michael Pinsker, Jakub
Rydval and Christoph Spiess.
en
dc.description.sponsorship
FWF - Österr. Wissenschaftsfonds
-
dc.language.iso
en
-
dc.subject
CSP
en
dc.subject
Logic
en
dc.subject
Constraint Satisfaction Problems
en
dc.subject
Bodirsky-Pinsker Conjecture
en
dc.title
Algebraicity is irrelevant (in the dichotomy conjecture for infinite-domain constraint satisfaction problems)
en
dc.type
Presentation
en
dc.type
Vortrag
de
dc.relation.grantno
I 5948-N
-
dc.type.category
Conference Presentation
-
tuw.project.title
Bedingungserfüllungsprobleme: jenseits des endlichen Falles
-
tuw.researchTopic.id
I1
-
tuw.researchTopic.name
Logic and Computation
-
tuw.researchTopic.value
100
-
tuw.publication.orgunit
E104-01 - Forschungsbereich Algebra
-
tuw.event.name
Summer School on General Algebra and Ordered Sets (SSAOS 2025)
en
tuw.event.startdate
07-09-2025
-
tuw.event.enddate
12-09-2025
-
tuw.event.online
On Site
-
tuw.event.type
Event for scientific audience
-
tuw.event.place
Blansko
-
tuw.event.country
CZ
-
tuw.event.institution
Prague
-
tuw.event.presenter
Schöbi, Moritz Albert
-
tuw.event.track
Single Track
-
wb.sciencebranch
Informatik
-
wb.sciencebranch
Mathematik
-
wb.sciencebranch.oefos
1020
-
wb.sciencebranch.oefos
1010
-
wb.sciencebranch.value
5
-
wb.sciencebranch.value
95
-
item.openairetype
conference paper not in proceedings
-
item.openairecristype
http://purl.org/coar/resource_type/c_18cp
-
item.cerifentitytype
Publications
-
item.languageiso639-1
en
-
item.grantfulltext
none
-
item.fulltext
no Fulltext
-
crisitem.author.dept
E104-01 - Forschungsbereich Algebra
-
crisitem.author.parentorg
E104 - Institut für Diskrete Mathematik und Geometrie
