Smooth approximations and CSPs over finitely bounded homogeneous structures

DOI10.1145/3531130.3533353MaRDI QIDQ6649468FDOQ6649468

Michael Pinsker, Antoine Mottet

Publication date: 6 December 2024

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Model theory of finite structures (03C13) Operations and polynomials in algebraic structures, primal algebras (08A40) Applications of universal algebra in computer science (08A70)

Cites Work

• Existence theorems for weakly symmetric operations
• Ramsey classes of set systems
• Transitivity of permutation groups on unordered sets
• Schaefer's theorem for graphs
• The reducts of equality up to primitive positive interdefinability
• Constraint Satisfaction with Countable Homogeneous Templates
• Non-dichotomies in Constraint Satisfaction Complexity
• The complexity of temporal constraint satisfaction problems
• On the Structure of Polynomial Time Reducibility
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Cores of Countably Categorical Structures
• The complexity of satisfiability problems
• Characterizations of several Maltsev conditions.
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• The structure of finite algebras
• Decidability of Definability
• Ontology-Based Data Access
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• \(H\)-coloring dichotomy revisited
• Minimal functions on the random graph
• Ramsey classes: examples and constructions
• Topological Birkhoff
• Bounded width problems and algebras
• Reducts of Ramsey structures
• Reducts of the random graph
• Discrete Temporal Constraint Satisfaction Problems
• The Complexity of Phylogeny Constraint Satisfaction
• The algebraic dichotomy conjecture for infinite domain Constraint Satisfaction Problems
• Principles and Practice of Constraint Programming – CP 2003
• All those Ramsey classes (Ramsey classes with closures and forbidden homomorphisms)
• A universal-algebraic proof of the complexity dichotomy for Monotone Monadic SNP
• Automorphism groups and Ramsey properties of sparse graphs
• CORES OVER RAMSEY STRUCTURES
• PROJECTIVE CLONE HOMOMORPHISMS
• Temporal Constraint Satisfaction Problems in Fixed-Point Logic
• Uniform Birkhoff
• The wonderland of reflections
• A Model-Theoretic View on Qualitative Constraint Reasoning
• A complexity dichotomy for poset constraint satisfaction
• A Proof of the CSP Dichotomy Conjecture
• A Dichotomy for First-Order Reducts of Unary Structures
• Equations in oligomorphic clones and the constraint satisfaction problem for ω-categorical structures
• Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction
• Constraint satisfaction problems for reducts of homogeneous graphs
• Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems)
• When Symmetries Are Not Enough: A Hierarchy of Hard Constraint Satisfaction Problems
• Universal Horn Sentences and the Joint Embedding Property
• A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP
• 𝜔-categorical structures avoiding height 1 identities
• On The Relational Width of First-Order Expansions of Finitely Bounded Homogeneous Binary Cores with Bounded Strict Width
• The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

This page was built for publication: Smooth approximations and CSPs over finitely bounded homogeneous structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6649468)