General lower bounds and improved algorithms for infinite-domain CSPs
From MaRDI portal
Publication:2700386
DOI10.1007/s00453-022-01017-8OpenAlexW4291001791MaRDI QIDQ2700386
Peter Jonsson, Victor Lagerkvist
Publication date: 21 April 2023
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-022-01017-8
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Strong partial clones and the time complexity of SAT problems
- An initial study of time complexity in infinite-domain constraint satisfaction
- The complexity of equality constraint languages
- Extendable local partial clones
- On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the Region Connection Calculus
- Endpoints of associated intervals for local clones on an infinite set
- The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems
- Building small equality graphs for deciding equality logic with uninterpreted functions
- Automata theory in nominal sets
- Incremental Satisfiability and Implication for UTVPI Constraints
- Precise Upper and Lower Bounds for the Monotone Constraint Satisfaction Problem
- A Model-Theoretic View on Qualitative Constraint Reasoning
- Complexity of Infinite-Domain Constraint Satisfaction
- Reasoning about temporal relations
- The Time Complexity of Constraint Satisfaction
- Non-dichotomies in Constraint Satisfaction Complexity
- The complexity of temporal constraint satisfaction problems
- The algebras of partial functions and their invariants
- Turing machines with atoms, constraint satisfaction problems, and descriptive complexity
- The algebraic dichotomy conjecture for infinite domain Constraint Satisfaction Problems
- A Dichotomy for First-Order Reducts of Unary Structures
- Sparsification of SAT and CSP Problems via Tractable Extensions
- Fine-Grained Time Complexity of Constraint Satisfaction Problems
- A Proof of the CSP Dichotomy Conjecture
- Turing Machines with Atoms
- Verification of Timed Automata via Satisfiability Checking
- Function Algebras on Finite Sets
- Partial Polymorphisms and Constraint Satisfaction Problems
- Slightly Superexponential Parameterized Problems
This page was built for publication: General lower bounds and improved algorithms for infinite-domain CSPs
