| ||||
| ||||
![]() Title:Smooth Approximations and CSPs over Finitely Bounded Homogeneous Structures Conference:LICS 2022 Tags:bounded width, canonical function, clone homomorphism, constraint satisfaction problem, dichotomy theorem, first order reduct, infinite-domain constraint satisfaction problem, local consistency, loop lemma, model complete core, polymorphism, smooth approximation and universal homogeneous tournament Abstract: We introduce the novel machinery of smooth approximations, and apply it to confirm the CSP dichotomy conjecture for first-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 significantly simplify the previous results from the literature. For all but the last structure, we moreover characterise for the first time those CSPs which are solvable by local consistency methods, again using the same machinery. Smooth Approximations and CSPs over Finitely Bounded Homogeneous Structures ![]() Smooth Approximations and CSPs over Finitely Bounded Homogeneous Structures | ||||
Copyright © 2002 – 2025 EasyChair |