Non-Redundancy of Low-Arity Symmetric Boolean CSPs

Amatya Sharma, Santhoshini Velusamy · 2026

Read Non-Redundancy of Low-Arity Symmetric Boolean CSPs by Amatya Sharma, Santhoshini Velusamy (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-14007.txt.

Introduction

Sharma and Velusamy study non-redundancy for low-arity symmetric Boolean constraint problems. Non-redundancy means the largest size of a problem instance with no smaller sub-instance sharing its satisfying assignments. It steers kernelization, exact and approximate sparsification, and exact streaming cost. For Boolean symmetric problems set by an r-ary relation whose value hinges only on Hamming weight, the paper gives a near-full classification of how non-redundancy grows.

Catalog record

CREATORAmatya Sharma, Santhoshini Velusamy
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE74896
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.14007

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Non-Redundancy of Low-Arity Symmetric Boolean CSPs Amatya Sharma, Santhoshini Velusamy Abstract Non-redundancy, introduced by Bessiere, Carbonnel, and Katsirelos (AAAI 2020), has emerged as a central structural parameter for Constraint Satisfaction Problems ( CSPs ): it underlies kernelization and exact sparsification, and recent work shows that it also governs approximate sparsification and exact streaming complexity. The non-redundancy NRD measures the largest size of a CSP instance that admits no smaller subinstance with the same set of satisfying assignments. In this paper we study the non-redundancy ( 𝖭𝖱𝖣 n ​ ( R ) \mathsf{NRD}_{n}(R) ) for Boolean symmetric CSPs specified by a symmetric r r -ary relation R R , that is, a relation whose value depends only on Hamming weight. An instance of CSP ( R ) (R) consists of n n variables and m m constraints, each given by an r r -tuple of variables, and a constraint is satisfied if and only if the resulting tuple belongs to R R . This is a natural and broad class containing Max-Cut , Max- k k -SAT , etc. Our main result is a near-complete classification of the growth of 𝖭𝖱𝖣 n ​ ( R ) \mathsf{NRD}_{n}(R) for symmetric Boolean predicates of arity at most 5 5 . Using computational experiments together with algebraic upper- and lower-bound criteria, we determine the asymptotic growth of 𝖭𝖱𝖣 n ​ ( R ) \mathsf{NRD}_{n}(R) for every symmetric Boolean predicate of arity at most 4 4 . At arity 5 5 , the framework resolves all predicates except two. On the upper-bound side, we introduce a lifted, higher-degree version of the balancedness notion of Chen, Jansen, and Pieterse (Algorithmica 2020), and show that it yields general upper bounds on non-redundancy. More precisely, we define t t -balancedness and prove that it is equivalent to the existence of degree at most t t multilinear polynomials “capturing” R R , implying that 𝖭𝖱𝖣 n ​ ( R ) = O ⁡ ( n t ) \mathsf{NRD}_{n}(R)=O(n^{t}) for every t t -balanced relation R R . On the lower-bound side, we use Carbonnel’s (CP 2022) framework, which gives a criterion for when a predicate admits a special reduction from the k k -ary OR relation; since OR already has non-redundancy Ω ⁡ ( n k ) \Omega(n^{k}) , this yields corresponding lower bounds on 𝖭𝖱𝖣 n ​ ( R ) \mathsf{NRD}_{n}(R) . While these determine the non-redundancy of symmetric predicates up to arity 4 4 and nearly all predicates of arity 5 5 , we discover two exceptional predicates of arity 5 5 that are not characterized by this framework—we obtain an Ω ⁡ ( n 2 ) \Omega(n^{2}) lower bound and an O ⁡ ( n 3 ) O(n^{3}) upper bound. We further show that these remaining cases reduce to natural extremal set-system questions. Independent Work. Very recently, Brakensiek, Guruswami, and Putterman [ 14 ] used a similar experimental viewpoint to study arity- 4 4 Boolean predicates, and one of their remaining cases connects to the symmetric arity- 5 5 predicate with W ( R 023 ) = { 0 , 2 , 3 } (R_{023})=\{0,2,3\} that also appears here. 1 Introduction Constraint satisfaction problems ( \mathsf{CSP} s) are a central framework in theoretical computer science. Formally, given a finite domain D and a constraint language \Gamma consisting of r -ary relations over D , an instance of \mathsf{CSP}(\Gamma) consists of n variables V:=\{x_{1},\ldots,x_{n}\} together with constraints of the form \{R,(\bar{x})\} , where R\in\Gamma and \bar{x}\in V^{r} . 1 1 1 Allowing unary maps on variables (e.g. literals in the Boolean case), constants, or repeated variables inside constraints does not change the asymptotic non-redundancy; see Section 6 . The goal is to decide whether there exists an assignment \sigma:V\to D such that (\sigma(x_{1}),\dots,\sigma(x_{r}))\in R for every constraint. This framework captures many familiar problems, including \mathsf{SAT} , graph coloring, and systems of local equations, and has been studied from the viewpoints of complexity theory [ 61 , 41 , 30 , 39 , 54 , 18 , 23 , 67 ] , approximation [ 51 , 50 , 58 , 9 , 1 , 27 , 52 , 60 , 46 , 6 , 37 , 59 , 34 , 53 , 21 , 35 , 2 , 42 , 8 , 43 , 4 , 3 ] , (approximate) sparsification [ 55 , 33 , 19 , 47 , 49 , 48 ] , kernelization and exact sparsification [ 28 , 40 , 22 , 57 , 10 , 20 , 17 , 12 , 13 ] , and, more recently, streaming and sketching [ 44 , 38 , 45 , 26 , 24 , 64 , 56 , 66 , 25 , 63 , 31 , 32 , 7 , 65 ] . Symmetric Boolean \mathsf{CSPs} . A relation R\subseteq\{0,1\}^{r} is symmetric if membership in R depends only on the Hamming weight of the input. Equivalently, there is a set \operatorname{W}(R)\subseteq\{0,1,\dots,r\} such that R=\{x\in\{0,1\}^{r}:|x|\in\operatorname{W}(R)\} . Thus a symmetric predicate can be specified simply by its set of accepted weights, and throughout the paper we will freely identify a symmetric predicate with its weight set \operatorname{W}(R) . Symmetric Boolean predicates already contain many natural and canonical problems. For example, the r -ary \operatorname{OR} predicate corresponds to \operatorname{W}(\operatorname{OR}_{r})=\{1,\dots,r\} and gives the usual r - \mathsf{SAT} constraints; the r -ary Not-All-Equal predicate corresponds to \operatorname{W}(\mathsf{NAE}_{r})=\{1,\dots,r-1\} and is closely related to hypergraph 2 -coloring and \mathsf{NAE} - \mathsf{SAT} ; threshold predicates correspond to intervals of the form \{t,t+1,\dots,r\} and capture “at least t ” type constraints; and parity predicates correspond to the even or odd weights and encode systems of linear equations over \mathbb{F}_{2} . For these reasons, symmetric predicates form a broad yet structured class, and they have been studied explicitly in work on approximation, sparsification, sketching, and non-redundancy [ 5 , 36 , 11 , 16 , 15 , 49 ] . Thus, we restrict our study to symmetric Boolean \mathsf{CSPs} in this paper. We ask how large can an instance be if every one of its constraints is non-redundant, that is, if no constraint can be removed without changing the satisfying set. This leads to the notion of non-redundancy. Non-redundancy. Given a \mathsf{CSP} instance, a constraint is redundant if deleting it does not change the set of satisfying assignments. An instance is non-redundant if every constraint is non-redundant in this sense. Following Bessiere, Carbonnel, and Katsirelos [ 10 ] , who introduced this viewpoint in the context of learning \mathsf{CSP} instances with few membership queries, and Carbonnel’s [ 20 ] subsequent structural study, we define the non-redundancy dimension of a constraint language \Gamma by \operatorname{NRD}_{n}(\Gamma):=\max\{|I|:I\text{ is a non-redundant }\mathsf{CSP}(\Gamma)\text{ instance on }n\text{ variables}\}. When \Gamma=\{R\} consists of a single relation, we also write \operatorname{NRD}_{n}(R) . Thus \operatorname{NRD}_{n}(R) asks a basic extremal question: how many R -constraints can be simultaneously non-redundant in an instance on n variables? At first sight, this is purely a combinatorial quantity. However, it turns out to be closely connected to several algorithmic and structural questions about \mathsf{CSPs} . Connections of \mathsf{NRD} to other problems. One such connection comes from exact sparsification . The goal is to reduce any n -variable instance in polynomial

Read the complete text