Optimal sparsification for some binary CSPs using low-degree polynomials

DOI10.1145/3349618MaRDI QIDQ5205824zbMATH OpenOpenAlexWikidataFDO

Authors Bart M. P. Jansen, Astrid Pieterse

Publication date 16 December 2019

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2016/6482/

zbMATH Keywords

constraint satisfaction problemkernelizationsatisfiabilitysparsification

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27) Computational aspects of satisfiability (68R07) Combinatorial optimization (90C27)

Recommendations

• Optimal sparsification for some binary CSPs using low-degree polynomials
• Best-case and worst-case sparsifiability of Boolean CSPs
• Best-case and worst-case sparsifiability of Boolean CSPs
• Sparsification of SAT and CSP Problems via Tractable Extensions
• Sparsification upper and lower bounds for graph problems and not-all-equal SAT

Cited in

(18)

• Acyclic orders, partition schemes and CSPs: unified hardness proofs and improved algorithms
• Sparsification upper and lower bounds for graph problems and not-all-equal SAT
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• Optimal sparsification for some binary CSPs using low-degree polynomials
• Parameterized Complexity of Conflict-Free Graph Coloring
• Best-case and worst-case sparsifiability of Boolean CSPs
• Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds
• Sparsification upper and lower bounds for graphs problems and not-all-equal SAT
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• Optimal polynomial-time compression for Boolean Max CSP
• Algebraic global gadgetry for surjective constraint satisfaction
• Kernelization for orthogonality dimension
• A near-optimal kernel for a coloring problem
• Optimal polynomial-time compression for Boolean Max CSP
• Kernelization for orthogonality dimension
• The complexity of contracting bipartite graphs into small cycles
• Kernelization for H-coloring
• Best-case and worst-case sparsifiability of Boolean CSPs

This page was built for publication: Optimal sparsification for some binary CSPs using low-degree polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5205824)