Smooth approximations and CSPs over finitely bounded homogeneous structures

Publikationstyp
Conference Paper
Date Issued
2022-08
Sprache
English
Author(s)
Mottet, Antoine  
Pinsker, Michael  
Institut
Theoretische Informatik E-EXK6  
TORE-URI
http://hdl.handle.net/11420/13585
Article Number
3533353
Citation
37th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2022)
Contribution to Conference
37th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2022  
Publisher DOI
10.1145/3531130.3533353
Scopus ID
2-s2.0-85136965438
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.