  CSP sparsification, introduced by Kogan and Krauthgamer (ITCS 2015),
considers the following question: when can an instance of a constraint
satisfaction problem be sparsified (by retaining a weighted subset of the
constraints) while still roughly capturing the weight of constraints satisfied
by {\em every} assignment. CSP sparsification generalizes and abstracts other
commonly studied problems including graph cut-sparsification, hypergraph
cut-sparsification and hypergraph XOR-sparsification. A central question here
is to understand what properties of a constraint predicate $P:\Sigma^r \to
\{0,1\}$ (where variables are assigned values in $\Sigma$) allow for nearly
linear-size sparsifiers (in the number of variables). In this work (1) we
significantly extend the class of CSPs for which nearly linear-size, and other
non-trivial, sparsifications exist and give classifications in some broad
settings and (2) give a polynomial-time algorithm to extract this
sparsification.
  Our results captured in item (1) completely classify all symmetric Boolean
predicates $P$ (i.e., on the Boolean domain $\Sigma = \{0,1\}$) that allow
nearly-linear-size sparsifications. Symmetric Boolean CSPs already capture all
the special classes of sparisifcation listed above including hypergraph
cut-sparsification and variants. Our study of symmetric CSPs reveals an
inherent, previously undetected, number-theoretic phenomenon that determines
near-linear size sparsifiability. We also completely classify the set of
Boolean predicates $P$ that allow non-trivial ($o(n^r)$-size) sparsifications,
thus answering an open question from the work of Kogan and Krauthgamer.
