Record link: 
http://hdl.handle.net/20.500.12708/191347
-
Title: 
Smooth approximations and CSPs over finitely bounded homogeneous structures
en
Citation: 
Mottet, A., & Pinsker, M. (2022). Smooth approximations and CSPs over finitely bounded homogeneous structures. In C. Baier (Ed.), Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science (pp. 1–13). https://doi.org/10.1145/3531130.3533353
-
Publisher DOI: 
10.1145/3531130.3533353
-
Publication Type: 
Inproceedings - Full-Paper Contribution
en
Language: 
English
-
Authors: 
Mottet, Antoine 
Pinsker, Michael 
-
Organisational Unit: 
E104-01 - Forschungsbereich Algebra 
-
Published in: 
Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science 
-
ISBN: 
9781450393515
-
Date (published): 
4-Aug-2022
-
Event name: 
LICS: Logic in Computer Science 2022 (LICS '22) 
en
Event date: 
2-Aug-2022 - 5-Aug-2022
-
Event place: 
Haifa, Israel
-
Number of Pages: 
13
-
Keywords: 
smooth approximations; Constraint Satisfaction Problem
en
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
Research Areas: 
Mathematical and Algorithmic Foundations: 95%
Computer Science Foundations: 5%
-
Science Branch: 
1020 - Informatik: 30%
1010 - Mathematik: 70%
-
Appears in Collections:
Conference Paper

Show full item record

Page view(s)

46
checked on Jan 10, 2024

Google ScholarTM

Check