Efficient Algorithms and New Characterizations for CSP Sparsification

CSP sparsification, introduced by Kogan and Krauthgamer (ITCS 2015), considers the following question: how much can an instance of a constraint satisfaction problem be sparsified (by retaining a reweighted subset of the constraints) while still roughly capturing the weight of constraints satisfied by every assignment. CSP sparsification captures as a special case several well-studied problems including graph cut-sparsification, hypergraph cut-sparsification, hypergraph XOR-sparsification, and corresponds to a general class of hypergraph sparsification problems where an arbitrary 0/1-valued splitting function is used to define the notion of cutting a hyperedge (see, for instance, Veldt-Benson-Kleinberg SIAM Review 2022). The main question here is to understand, for a given constraint predicate P :Σ r → {0,1} (where variables are assigned values in Σ), the smallest constant c such that O ( n c ) sized sparsifiers exist for every instance of a constraint satisfaction problem over P . A recent work of Khanna, Putterman and Sudan (SODA 2024) [KPS24] showed existence of near-linear size sparsifiers for new classes of CSPs. In this work, (1) we significantly extend the class of CSPs for which nearly linear-size sparsifications can be shown to exist while also extending the scope to settings with non-linear-sized sparsifications; (2) we give a polynomial-time algorithm to extract such sparsifications for all the problems we study including the first efficient sparsification algorithms for the problems studied in [KPS24]. Our results captured in item (1) lead to two new classifications: First we get a complete classification of all symmetric Boolean predicates P (i.e., on the Boolean domain Σ = {0,1}) that allow nearly-linear-size sparsifications. This classification reveals an inherent, and previously unsuspected, number-theoretic phenomenon that determines near-linear size sparsifiability. Second, 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. The constructive aspect of our result is an arguably unexpected strengthening of [KPS24]. Their work roughly seemed to suggest that sparsifications can be found by solving problems related to finding the minimum distance of linear codes. These problems remain unsolved (in fact, are NP-hard) to this date and our work finds a different path to achieve poly-time sparsification, resolving an open problem from their work. As a consquence we also get the first efficient algorithms to spectrally sparsify Cayley graphs over F 2 n in time polynomial in the number of generators. Our techniques build on [KPS24] which proves the existence of nearly-linear size sparsifiers for CSPs where the unsatisfying assignments of the underlying predicate P are given by a linear equation over a finite field. Our main contributions are to extend this framework to higher-degree equations over general Abelian groups (both elements are crucial for our classification results) as well as designing polynomial-time sparsification algorithms for all problems in our framework.

Authors

• Sanjeev Khanna
• Aaron Putterman
• Madhu Sudan 0001

Keywords

• Constraint satisfaction problems
• sparsification