Best-case and worst-case sparsifiability of Boolean CSPs
From MaRDI portal
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27) Computational aspects of satisfiability (68R07)
Recommendations
- Best-case and worst-case sparsifiability of Boolean CSPs
- Optimal sparsification for some binary CSPs using low-degree polynomials
- Optimal sparsification for some binary CSPs using low-degree polynomials
- Sparsification of SAT and CSP Problems via Tractable Extensions
- Sparsification of two-variable valued constraint satisfaction problems
Cites work
- scientific article; zbMATH DE number 3661343 (Why is no real title available?)
- Classifying the Complexity of Constraints Using Finite Algebras
- Fundamentals of parameterized complexity
- Kernel bounds for disjoint cycles and disjoint paths
- Kernelization -- preprocessing with a guarantee
- Kernelization Lower Bounds by Cross-Composition
- Kernelization of packing problems
- New limits to classical and quantum instance compression
- Optimal data reduction for graph coloring using low-degree polynomials
- Optimal sparsification for some binary CSPs using low-degree polynomials
- Optimal sparsification for some binary CSPs using low-degree polynomials
- Parameterized algorithms
- Point line cover: the easy kernel is essentially tight
- Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Sparsification upper and lower bounds for graph problems and not-all-equal SAT
- The complexity of satisfiability problems
- The power of primitive positive definitions with polynomially many variables
- Weak bases of Boolean co-clones
Cited in
(12)- Optimal sparsification for some binary CSPs using low-degree polynomials
- Optimal sparsification for some binary CSPs using low-degree polynomials
- Additive Sparsification of CSPs.
- scientific article; zbMATH DE number 7651202 (Why is no real title available?)
- Sparsification of Binary CSPs
- Algebraic global gadgetry for surjective constraint satisfaction
- Sparsification of two-variable valued constraint satisfaction problems
- Sparsification lower bounds for list \(H\)-coloring
- Sparsification of binary CSPs
- Sparsification lower bound for linear spanners in directed graphs
- The algebraic structure of the densification and the sparsification tasks for CSPs
- Best-case and worst-case sparsifiability of Boolean CSPs
This page was built for publication: Best-case and worst-case sparsifiability of Boolean CSPs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q786033)
