General lower bounds and improved algorithms for infinite-domain CSPs

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

zbMATH Keywords

lower boundsconstraint satisfactioninfinite domainsfine-grained complexityequality languages

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

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