<div class="csl-bib-body">
<div class="csl-entry">Semanisinova, Z., Bodirsky, M., Jahel, C., & Mottet, A. (2026, February 6). <i>A Preservation Theorem for Valued Structures</i> [Conference Presentation]. 108th Workshop on General Algebra, Wien, Austria. http://hdl.handle.net/20.500.12708/226456</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/226456
-
dc.description.abstract
The algebraic approach to constraint satisfaction problems (CSPs) has been very fruitful
for classifying computational complexity. This approach is based on the interplay of
polymorphisms, which are operations that preserve all relations of the CSP template,
and of relations that are primitively positively definable in the template. A central
result in the area is the so-called preservation theorem, due to Bodirsky and Nešetřil for
infinite-domain templates, which states that a relation is primitively positively definable
in a relational structure A if and only if it is preserved by all polymorphisms of A.
Valued CSPs are a natural generalization of CSPs that allows to model optimization
problems by replacing relations in the template by cost functions. For valued CSPs
over finite-domain templates a preservation theorem was proved by Fulla and Živný,
using the more general concepts of fractional polymorphisms and expressibility instead
of polymorphisms and primitive positive definability. The focus of this talk is an ongoing
project towards a common generalization of the result of Bodirsky and Nešetřil and of
Fulla and Živný for valued CSPs over infinite-domain templates. We conjecture that
given a valued structure Γ with an oligomorphic automorphism group, a valued relation R
is expressible in Γ if and only if R is improved by all fractional polymorphisms of Γ. If
true, this result would have far-reaching consequences related to the complexity of valued
CSPs and to the algebraic structure of templates for valued CSPs, e.g., existence of cores.
en
dc.description.sponsorship
FWF - Österr. Wissenschaftsfonds
-
dc.language.iso
en
-
dc.subject
valued CSPs
en
dc.subject
fractional polymorphisms
en
dc.subject
expressive power
en
dc.subject
preservation theorem
en
dc.title
A Preservation Theorem for Valued Structures
en
dc.type
Presentation
en
dc.type
Vortrag
de
dc.contributor.affiliation
Technische Universität Dresden, Germany
-
dc.contributor.affiliation
American University of Beirut, Lebanon
-
dc.contributor.affiliation
Technische Universität Hamburg, Germany
-
dc.relation.grantno
ESP6949724
-
dc.type.category
Conference Presentation
-
tuw.project.title
Komplexität von Optimierung: VCSPs auf unendlichen Mengen
-
tuw.researchTopic.id
I1
-
tuw.researchTopic.id
A3
-
tuw.researchTopic.name
Logic and Computation
-
tuw.researchTopic.name
Fundamental Mathematics Research
-
tuw.researchTopic.value
20
-
tuw.researchTopic.value
80
-
tuw.publication.orgunit
E104-01 - Forschungsbereich Algebra
-
tuw.author.orcid
0000-0001-8111-0671
-
tuw.author.orcid
0000-0002-3517-1745
-
tuw.event.name
108th Workshop on General Algebra
en
dc.description.sponsorshipexternal
European Research Council
-
dc.relation.grantnoexternal
ERC Synergy Grant 101071674
-
tuw.event.startdate
06-02-2026
-
tuw.event.enddate
08-02-2026
-
tuw.event.online
On Site
-
tuw.event.type
Event for scientific audience
-
tuw.event.place
Wien
-
tuw.event.country
AT
-
tuw.event.institution
TU Wien
-
tuw.event.presenter
Semanisinova, Zaneta
-
wb.sciencebranch
Informatik
-
wb.sciencebranch
Mathematik
-
wb.sciencebranch.oefos
1020
-
wb.sciencebranch.oefos
1010
-
wb.sciencebranch.value
5
-
wb.sciencebranch.value
95
-
item.openairecristype
http://purl.org/coar/resource_type/c_18cp
-
item.fulltext
no Fulltext
-
item.languageiso639-1
en
-
item.grantfulltext
restricted
-
item.openairetype
conference paper not in proceedings
-
item.cerifentitytype
Publications
-
crisitem.author.dept
E104-01 - Forschungsbereich Algebra
-
crisitem.author.dept
Technische Universität Dresden, Germany
-
crisitem.author.dept
American University of Beirut, Lebanon
-
crisitem.author.dept
Technische Universität Hamburg, Germany
-
crisitem.author.orcid
0000-0001-8111-0671
-
crisitem.author.orcid
0000-0002-3517-1745
-
crisitem.author.parentorg
E104 - Institut für Diskrete Mathematik und Geometrie
