2020/11/08 by Antoine Mottet, Mottet, Antoine, Michael Pinsker +1 · 1 citation
Mathematics · #Advanced Operator Algebra Research #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #Logic in Computer Science (cs.LO) #Markov Chains and Monte Carlo Methods #Random Matrices and Applications #Rings and Algebras (math.RA)
paper · pdf · doi:10.48550/arxiv.2011.03978
openalex publication_date 2020/11/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
We develop the novel machinery of smooth approximations, and apply it to confirm the CSP dichotomy conjecture for first-order reducts of the random tournament, various homogeneous graphs including the random graph, and for expansions of the order of the rationals. 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 characterize those CSPs which are solvable by local consistency methods, again using the same machinery.