Publication:5089260

DOI10.4230/LIPIcs.MFCS.2020.85MaRDI QIDQ5089260

Stanislav Živný, Caterina Viola

Publication date: 18 July 2022

zbMATH Keywords

convex relaxations; polymorphisms; valued constraint satisfaction; promise constraint satisfaction

Mathematics Subject Classification ID

68Qxx: Theory of computing

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Constraint satisfaction and semilinear expansions of addition over the rationals and the reals
• Correlation clustering
• Results on the propositional \(\mu\)-calculus
• Geometric algorithms and combinatorial optimization.
• Schaefer's Theorem for Graphs
• Robustly Solvable Constraint Satisfaction Problems
• Linear programming, width-1 CSPs, and robust satisfaction
• Lower Bounds on the Size of Semidefinite Programming Relaxations
• On the usefulness of predicates
• Robust Satisfiability for CSPs
• Essential Convexity and Complexity of Semi-Algebraic Constraints
• Approximation Resistance from Pairwise-Independent Subgroups
• Approximate Constraint Satisfaction Requires Large LP Relaxations
• The Complexity of Finite-Valued CSPs
• Algebraic Properties of Valued Constraint Satisfaction Problem
• Non-dichotomies in Constraint Satisfaction Complexity
• The complexity of temporal constraint satisfaction problems
• Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
• Algorithms for the Solution of Systems of Linear Diophantine Equations
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Discrete Temporal Constraint Satisfaction Problems
• The Limits of SDP Relaxations for General-Valued CSPs
• Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs
• Symmetric Polymorphisms and Efficient Decidability of Promise CSPs
• CSP gaps and reductions in the lasserre hierarchy
• Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs
• 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
• An Algorithmic Blend of LPs and Ring Equations for Promise CSPs
• The Power of Linear Programming for General-Valued CSPs
• The Complexity of General-Valued CSPs
• Classifying the Complexity of Constraints Using Finite Algebras
• The Power of Sherali--Adams Relaxations for General-Valued CSPs
• The Complexity of Phylogeny Constraint Satisfaction Problems
• The complexity of satisfiability problems