Optimal Sparsification for Some Binary CSPs Using Low-Degree Polynomials

DOI10.4230/LIPIcs.MFCS.2016.71zbMath1398.68244arXiv1606.03233OpenAlexW2988908508MaRDI QIDQ4608634

Bart M. P. Jansen, Astrid Pieterse

Publication date: 21 March 2018

Full work available at URL: https://arxiv.org/abs/1606.03233

zbMATH Keywords

satisfiabilityconstraint satisfaction problemsparsificationkernelization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (6)

Sparsification upper and lower bounds for graph problems and not-all-equal SAT ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Optimal data reduction for graph coloring using low-degree polynomials ⋮ Optimal Data Reduction for Graph Coloring Using Low-Degree Polynomials ⋮ 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