DC Field
Value
Language
dc.contributor.author
Rydval, Jakub
-
dc.date.accessioned
2026-01-22T14:13:29Z
-
dc.date.available
2026-01-22T14:13:29Z
-
dc.date.issued
2025-12-19
-
dc.identifier.citation
<div class="csl-bib-body"> <div class="csl-entry">Rydval, J. (2025). Fundamental Questions in Modern Infinite-Domain Constraint Satisfaction. In <i>The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 25211)</i>. The Constraint Satisfaction Problem: Complexity and Approximability, Dagstuhl, Germany. Schloss Dagstuhl - Leibniz-Zentrum für Informatik.</div> </div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/225302
-
dc.description.abstract
The Feder-Vardi dichotomy conjecture for Constraint Satisfaction Problems (CSPs) with finite templates, confirmed independently by Bulatov and Zhuk, has an extension to certain well-behaved infinite templates due to Bodirsky and Pinsker which remains wide open. In this talk, I motivate several fundamental questions on the scope of the Bodirsky-Pinsker conjecture and provide answers to some of them. This concerns, e.g., identifying model-theoretic assumptions that can be added without loss of generality or finding general connections to finite-domain promise CSPs. The presented material stems from joint work with Michael Pinsker, Moritz Schöbi, and Christoph Spiess.
en
dc.description.sponsorship
FWF - Österr. Wissenschaftsfonds
-
dc.language.iso
en
-
dc.subject
(Promise) Constraint Satisfaction Problem, dichotomy conjecture, polymorphism, identity, algebraicity, homogeneity, ω-categoricity, finite boundedness, Datalog
-
dc.title
Fundamental Questions in Modern Infinite-Domain Constraint Satisfaction
en
dc.type
Inproceedings
en
dc.type
Konferenzbeitrag
de
dc.relation.doi
10.4230/DagRep.15.5.114
-
dc.relation.grantno
I 5948-N
-
dc.type.category
Abstract Book Contribution
-
tuw.booktitle
The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 25211)
-
tuw.container.volume
15
-
tuw.book.ispartofseries
Dagstuhl Reports
-
tuw.relation.publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
-
tuw.publication.invited
invited
-
tuw.project.title
Bedingungserfüllungsprobleme: jenseits des endlichen Falles
-
tuw.researchTopic.id
C4
-
tuw.researchTopic.id
C5
-
tuw.researchTopic.name
Mathematical and Algorithmic Foundations
-
tuw.researchTopic.name
Computer Science Foundations
-
tuw.researchTopic.value
40
-
tuw.researchTopic.value
60
-
tuw.publication.orgunit
E104-01 - Forschungsbereich Algebra
-
dc.description.numberOfPages
1
-
tuw.event.name
The Constraint Satisfaction Problem: Complexity and Approximability
en
tuw.event.startdate
18-05-2025
-
tuw.event.enddate
23-05-2025
-
tuw.event.online
On Site
-
tuw.event.type
Event for scientific audience
-
tuw.event.place
Dagstuhl
-
tuw.event.country
DE
-
tuw.event.presenter
Rydval, Jakub
-
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
-
item.openairecristype
http://purl.org/coar/resource_type/c_5794
-
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
-
crisitem.project.funder
FWF - Österr. Wissenschaftsfonds
-
crisitem.project.grantno
I 5948-N
-
Appears in Collections:
Conference Paper
Show simple item record

Google ScholarTM

Check