Complexity of infinite-domain constraint satisfaction

Categoricity and completeness of theories (03C35) Applications of model theory (03C98) Ramsey theory (05D10) Applications of universal algebra in computer science (08A70) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Computational aspects of satisfiability (68R07)

Recommendations

The complexity of constraint satisfaction: an algebraic approach
Complexity classifications of Boolean constraint satisfaction problems
Universal Algebra and Hardness Results for Constraint Satisfaction Problems
Complexity of conservative constraint satisfaction problems
On the scope of the universal-algebraic approach to constraint satisfaction

Cited in

(60)

Maximal infinite-valued constraint languages
The wonderland of reflections
Homogeneous structures: model theory meets universal algebra. Abstracts from the workshop held January 3--9, 2021 (online meeting)
Minimal inference problem over finite domains: the landscape of complexity
General lower bounds and improved algorithms for infinite-domain CSPs
On the scope of the universal-algebraic approach to constraint satisfaction
Constraint satisfaction tractability from semi-lattice operations on infinite sets
Non-dichotomies in Constraint Satisfaction Complexity
Collapsibility in Infinite-Domain Quantified Constraint Satisfaction
Locally finite constraint satisfaction problems
The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems
Universal Horn Sentences and the Joint Embedding Property
When symmetries are not enough: a hierarchy of hard constraint satisfaction problems
Tractable combinations of temporal CSPs
Local–global property for G-invariant terms
Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems)
Maximal Infinite-Valued Constraint Languages
Constraint Satisfaction Problems with Infinite Templates
Computational Short Cuts in Infinite Domain Constraint Satisfaction
The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom
The smallest hard trees
\((\mathbb{Z},\mathrm{succ},U)\), \((\mathbb{Z},E,U)\), and their CSP's
The lattice of clones of self-dual operations collapsed
On guarded extensions of MMSNP
Solving infinite-domain CSPs using the patchwork property
The complexity of recursive constraint satisfaction problems
Unifying the three algebraic approaches to the CSP via minimal Taylor algebras
On the descriptive complexity of temporal constraint satisfaction problems
Complexity classification transfer for CSPs via algebraic products
Exploring new topologies for the theory of clones
Canonical polymorphisms of Ramsey structures and the unique interpolation property
Topology is relevant (in a dichotomy conjecture for infinite-domain constraint satisfaction problems)
Collapsing the bounded width hierarchy for infinite-domain constraint satisfaction problems: when symmetries are enough
Forbidden tournaments and the orientation completion problem
On guarded extensions of MMSNP
An algebraic proof of the dichotomy for graph orientation problems with forbidden tournaments
Identifying tractable quantified temporal constraints within Ord-Horn
Homogeneity and homogenizability: hard problems for the logic SNP
Solving promise equations over monoids and groups
Parameterized complexity classification for interval constraints
Infinitary primitive positive definability over the real numbers with convex relations
The generic circular triangle-free graph
The complexity of resilience problems via valued constraint satisfaction problems
Algebraic approach to approximation
Smooth approximations: an algebraic approach to CSPs over finitely bounded homogeneous structures
On when the union of two algebraic sets is algebraic
A complexity dichotomy in spatial reasoning via Ramsey theory
Solving promise equations over monoids and groups
GMSNP and finite structures
Algorithms and complexity of difference logic
Specification and automatic verification of computational reductions
Datalog-expressibility for monadic and guarded second-order logic
Datalog-expressibility for monadic and guarded second-order logic
Clones of Borel Boolean functions
Temporal valued constraint satisfaction problems
Polynomial-time tractable problems over the p-adic numbers
Three fundamental questions in modern infinite-domain constraint satisfaction
The complexity of resilience problems via valued constraint satisfaction
Satisfiability of commutative vs. non-commutative CSPs
Maximum and- vs. even-SAT

This page was built for publication: Complexity of infinite-domain constraint satisfaction

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