Conditional dichotomy of Boolean ordered promise CSPs
From MaRDI portal
Publication:6566587
DOI10.46298/THEORETICS.23.2MaRDI QIDQ6566587FDOQ6566587
Authors: Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep 
Publication date: 3 July 2024
Published in: TheoretiCS (Search for Journal in Brave)
Cites Work
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Closure properties of constraints
- Analysis of Boolean Functions
- Classifying the Complexity of Constraints Using Finite Algebras
- The complexity of satisfiability problems
- On the algebraic structure of combinatorial problems
- On the power of unique 2-prover 1-round games
- Efficient computation of the Shapley value for game-theoretic network centrality
- A Parallel Repetition Theorem
- Galois theory for minors of finite functions
- An approximate zero-one law
- New hardness results for graph and hypergraph colorings
- Social Indeterminacy
- On independent sets, 2-to-2 games, and Grassmann graphs
- \((2+\varepsilon)\)-Sat is NP-hard
- Improved hardness for \(H\)-colourings of \(G\)-colourable graphs
- A proof of the CSP dichotomy conjecture
- Algebraic Approach to Promise Constraint Satisfaction
- Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
- 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?
- On non-optimally expanding sets in Grassmann graphs
- 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)
- Rainbow coloring hardness via low sensitivity polymorphisms
- Title not available (Why is that?)
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)
