  We continue the investigation of polynomial-time sparsification for
NP-complete Boolean Constraint Satisfaction Problems (CSPs). The goal in
sparsification is to reduce the number of constraints in a problem instance
without changing the answer, such that a bound on the number of resulting
constraints can be given in terms of the number of variables n. We investigate
how the worst-case sparsification size depends on the types of constraints
allowed in the problem formulation (the constraint language). Two algorithmic
results are presented. The first result essentially shows that for any arity k,
the only constraint type for which no nontrivial sparsification is possible has
exactly one falsifying assignment, and corresponds to logical OR (up to
negations). Our second result concerns linear sparsification, that is, a
reduction to an equivalent instance with O(n) constraints. Using linear algebra
over rings of integers modulo prime powers, we give an elegant necessary and
sufficient condition for a constraint type to be captured by a degree-1
polynomial over such a ring, which yields linear sparsifications. The
combination of these algorithmic results allows us to prove two
characterizations that capture the optimal sparsification sizes for a range of
Boolean CSPs. For NP-complete Boolean CSPs whose constraints are symmetric (the
satisfaction depends only on the number of 1 values in the assignment, not on
their positions), we give a complete characterization of which constraint
languages allow for a linear sparsification. For Boolean CSPs in which every
constraint has arity at most three, we characterize the optimal size of
sparsifications in terms of the largest OR that can be expressed by the
constraint language.
