A separator theorem for hypergraphs and a CSP-SAT algorithm
From MaRDI portal
Recommendations
- New exact algorithms for the 2-constraint satisfaction problem
- Improved algorithms for sparse MAX-SAT and MAX-k-CSP
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Strong Refutation Heuristics for Random k-SAT
- Separate, measure and conquer: faster polynomial-space algorithms for Max 2-CSP and counting dominating sets
Cites work
- 3-coloring in time
- A characterization of tree-like resolution size
- Algorithms – ESA 2005
- An improved exponential-time algorithm for k -SAT
- Automating resolution is NP-hard
- Boolean function complexity. Advances and frontiers.
- Hard examples for resolution
- scientific article; zbMATH DE number 1452705 (Why is no real title available?)
- scientific article; zbMATH DE number 1445296 (Why is no real title available?)
- scientific article; zbMATH DE number 7561762 (Why is no real title available?)
- Improved algorithms for sparse MAX-SAT and MAX-k-CSP
- Improving resolution width lower bounds for k-CNFs with applications to the strong exponential time hypothesis
- Nearly perfect matchings in regular simple hypergraphs
- Packing paths in Steiner triple systems
- Proof Complexity
- Random CNF's are hard for the polynomial calculus
- Set partitioning via inclusion-exclusion
- Short proofs are narrow—resolution made simple
- Strong ETH and resolution via games and the multiplicity of strategies
- Strong ETH holds for regular resolution
- The isoperimetric number of random regular graphs
- The Time Complexity of Constraint Satisfaction
This page was built for publication: A separator theorem for hypergraphs and a CSP-SAT algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5028438)
