Optimal Sparsification for Some Binary CSPs Using Low-degree Polynomials

Bart M. P. Jansen, Astrid Pieterse

This paper analyzes to what extent it is possible to efficiently reduce the number of clauses in NP-hard satisfiability problems, without changing the answer. Upper and lower bound…