Best-case and worst-case sparsifiability of Boolean CSPs
From MaRDI portal
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27) Computational aspects of satisfiability (68R07) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
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
- Classifying the Complexity of Constraints Using Finite Algebras
- Fundamentals of parameterized complexity
- scientific article; zbMATH DE number 3661343 (Why is no real title available?)
- 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
(14)- Sparsification lower bound for linear spanners in directed graphs
- Optimal sparsification for some binary CSPs using low-degree polynomials
- Best-case and worst-case sparsifiability of Boolean CSPs
- Sparsification of Binary CSPs
- Optimal sparsification for some binary CSPs using low-degree polynomials
- Sparsification of binary CSPs
- Sparsification of two-variable valued constraint satisfaction problems
- Optimal polynomial-time compression for Boolean Max CSP
- Sparsification lower bounds for list \(H\)-coloring
- Additive Sparsification of CSPs.
- The algebraic structure of the densification and the sparsification tasks for CSPs
- Algebraic global gadgetry for surjective constraint satisfaction
- A near-optimal kernel for a coloring problem
- Optimal polynomial-time compression for Boolean Max CSP
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)
