<div class="csl-bib-body">
<div class="csl-entry">Mottet, A., & Pinsker, M. (2022). Smooth approximations and CSPs over finitely bounded homogeneous structures. In C. Baier (Ed.), <i>Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science</i> (pp. 1–13). https://doi.org/10.1145/3531130.3533353</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/191347
-
dc.description.abstract
We introduce the novel machinery of smooth approximations, and apply it to confrm the CSP dichotomy conjecture for frst-order reducts of the random tournament, and to give new short proofs of the conjecture for various homogeneous graphs including the random graph (STOC'11, ICALP'16), and for expansions of the order of the rationals (STOC'08). Apart from obtaining these dichotomy results, we show how our new proof technique allows to unify and signifcantly simplify the previous results from the literature. For all but the last structure, we moreover characterize for the frst time those CSPs which are solvable by local consistency methods, again using the same machinery.
en
dc.language.iso
en
-
dc.subject
smooth approximations
en
dc.subject
Constraint Satisfaction Problem
en
dc.title
Smooth approximations and CSPs over finitely bounded homogeneous structures
en
dc.type
Inproceedings
en
dc.type
Konferenzbeitrag
de
dc.contributor.affiliation
Hamburg University of Technology, Germany
-
dc.contributor.editoraffiliation
TU Dresden, Germany
-
dc.relation.isbn
9781450393515
-
dc.description.startpage
1
-
dc.description.endpage
13
-
dc.type.category
Full-Paper Contribution
-
tuw.booktitle
Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science
-
tuw.researchTopic.id
C4
-
tuw.researchTopic.id
C5
-
tuw.researchTopic.name
Mathematical and Algorithmic Foundations
-
tuw.researchTopic.name
Computer Science Foundations
-
tuw.researchTopic.value
95
-
tuw.researchTopic.value
5
-
tuw.publication.orgunit
E104-01 - Forschungsbereich Algebra
-
tuw.publisher.doi
10.1145/3531130.3533353
-
dc.description.numberOfPages
13
-
tuw.author.orcid
0000-0002-3517-1745
-
tuw.event.name
LICS: Logic in Computer Science 2022 (LICS '22)
en
tuw.event.startdate
02-08-2022
-
tuw.event.enddate
05-08-2022
-
tuw.event.online
On Site
-
tuw.event.type
Event for scientific audience
-
tuw.event.place
Haifa
-
tuw.event.country
IL
-
tuw.event.presenter
Pinsker, Michael
-
wb.sciencebranch
Informatik
-
wb.sciencebranch
Mathematik
-
wb.sciencebranch.oefos
1020
-
wb.sciencebranch.oefos
1010
-
wb.sciencebranch.value
30
-
wb.sciencebranch.value
70
-
item.languageiso639-1
en
-
item.openairetype
conference paper
-
item.grantfulltext
none
-
item.fulltext
no Fulltext
-
item.cerifentitytype
Publications
-
item.openairecristype
http://purl.org/coar/resource_type/c_5794
-
crisitem.author.dept
Hamburg University of Technology
-
crisitem.author.dept
E104-01 - Forschungsbereich Algebra
-
crisitem.author.orcid
0000-0002-3517-1745
-
crisitem.author.parentorg
E104 - Institut für Diskrete Mathematik und Geometrie
