𝜔-categorical structures avoiding height 1 identities

DOI10.1090/tran/8179zbMath1472.08006arXiv2006.12254OpenAlexW3101271171MaRDI QIDQ5141754

Michael Pinsker, Manuel Bodirsky, Antoine Mottet, Ross Willard, Jakub Opršal, Miroslav Olšák

Publication date: 18 December 2020

Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2006.12254

zbMATH Keywords

constraint satisfaction problemcomplexity dichotomyhomogeneous structurepointwise convergence topologyMal'cev conditionorbit growthfinite boundedness\( \omega \)-categoricitynonnested identity

Mathematics Subject Classification ID

Applications of universal algebra in computer science (08A70) Complexity of computation (including implicit computational complexity) (03D15) Equational logic, Mal'tsev conditions (08B05) Equational classes, universal algebra in model theory (03C05) Quantifier elimination, model completeness, and related topics (03C10)

Related Items (3)

CLAP: A New Algorithm for Promise CSPs ⋮ When Symmetries Are Not Enough: A Hierarchy of Hard Constraint Satisfaction Problems ⋮ A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A strong Mal'cev condition for locally finite varieties omitting the unary type
• The chromatic number of the product of two 4-chromatic graphs is 4
• Some very weak identities
• Polynomial interpolation and the Chinese remainder theorem for algebraic systems
• Universal graphs with forbidden subgraphs and algebraic closure
• The hardness of approximate optima in lattices, codes, and systems of linear equations
• Uniform Birkhoff
• The wonderland of reflections
• Counterexamples to Hedetniemi's conjecture
• Schaefer's Theorem for Graphs
• A Model-Theoretic View on Qualitative Constraint Reasoning
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• Constraint Satisfaction with Countable Homogeneous Templates
• Non-dichotomies in Constraint Satisfaction Complexity
• The complexity of temporal constraint satisfaction problems
• The structure of finite algebras
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Homomorphism and embedding universal structures for restricted classes
• The weakest nontrivial idempotent equations
• The algebraic dichotomy conjecture for infinite domain Constraint Satisfaction Problems
• A complexity dichotomy for poset constraint satisfaction
• Equations in oligomorphic clones and the constraint satisfaction problem for ω-categorical structures
• PROJECTIVE CLONE HOMOMORPHISMS
• A universal-algebraic proof of the complexity dichotomy for Monotone Monadic SNP
• Algebraic approach to promise constraint satisfaction
• Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems)
• Constraint Satisfaction Problems for Reducts of Homogeneous Graphs
• Cores of Countably Categorical Structures
• Classifying the Complexity of Constraints Using Finite Algebras
• The Complexity of Phylogeny Constraint Satisfaction Problems
• Topological Birkhoff
• Algebras Whose Congruence Lattices are Distributive.

This page was built for publication: 𝜔-categorical structures avoiding height 1 identities