Conditional dichotomy of Boolean ordered promise CSPs
From MaRDI portal
Publication:6566587
Cites work
- scientific article; zbMATH DE number 7561550 (Why is no real title available?)
- 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)
- A Parallel Repetition Theorem
- A proof of the CSP dichotomy conjecture
- Algebraic Approach to Promise Constraint Satisfaction
- An approximate zero-one law
- Analysis of Boolean Functions
- Classifying the Complexity of Constraints Using Finite Algebras
- Closure properties of constraints
- Efficient computation of the Shapley value for game-theoretic network centrality
- Galois theory for minors of finite functions
- Improved hardness for \(H\)-colourings of \(G\)-colourable graphs
- New hardness results for graph and hypergraph colorings
- On independent sets, 2-to-2 games, and Grassmann graphs
- On non-optimally expanding sets in Grassmann graphs
- On the algebraic structure of combinatorial problems
- On the power of unique 2-prover 1-round games
- Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
- Rainbow coloring hardness via low sensitivity polymorphisms
- Social Indeterminacy
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- The complexity of satisfiability problems
- The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems
- Towards a proof of the 2-to-1 games conjecture?
- \((2+\varepsilon)\)-Sat is NP-hard
This page was built for publication: Conditional dichotomy of Boolean ordered promise CSPs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6566587)
