We initiate the study of spectral sparsification for instances of Constraint
Satisfaction Problems (CSPs). In particular, we introduce a notion of the
\emph{spectral energy} of a fractional assignment for a Boolean CSP instance,
and define a \emph{spectral sparsifier} as a weighted subset of constraints
that approximately preserves this energy for all fractional assignments. Our
definition not only strengthens the combinatorial notion of a CSP sparsifier
but also extends well-studied concepts such as spectral sparsifiers for graphs
and hypergraphs.
Recent work by Khanna, Putterman, and Sudan [SODA 2024] demonstrated
near-linear sized \emph{combinatorial sparsifiers} for a broad class of CSPs,
which they term \emph{field-affine CSPs}. Our main result is a polynomial-time
algorithm that constructs a spectral CSP sparsifier of near-quadratic size for
all field-affine CSPs. This class of CSPs includes graph (and hypergraph) cuts,
XORs, and more generally, any predicate which can be written as $P(x_1, \dots
x_r) = \mathbf{1}[\sum a_i x_i \neq b \mod p]$.
Based on our notion of the spectral energy of a fractional assignment, we
also define an analog of the second eigenvalue of a CSP instance. We then show
an extension of Cheeger’s inequality for all even-arity XOR CSPs, showing that
this second eigenvalue loosely captures the “expansion” of the underlying
CSP. This extension specializes to the case of Cheeger’s inequality when all
constraints are even XORs and thus gives a new generalization of this powerful
inequality which converts the combinatorial notion of expansion to an analytic
property.

Este artículo explora los viajes en el tiempo y sus implicaciones.

Descargar PDF: