Publication:5089260
From MaRDI portal
DOI10.4230/LIPIcs.MFCS.2020.85MaRDI QIDQ5089260
Stanislav Živný, Caterina Viola
Publication date: 18 July 2022
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