Optimal Sparsification for Some Binary CSPs Using Low-Degree Polynomials

DOI10.1145/3349618zbMath1495.68100OpenAlexW2963798801WikidataQ127308066 ScholiaQ127308066MaRDI QIDQ5205824

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

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) Parameterized complexity, tractability and kernelization (68Q27) Computational aspects of satisfiability (68R07)

Related Items (6)

Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Acyclic orders, partition schemes and CSPs: unified hardness proofs and improved algorithms ⋮ Parameterized Complexity of Conflict-Free Graph 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