Recognition: no theorem link
Non-Redundancy of Low-Arity Symmetric Boolean CSPs
Pith reviewed 2026-05-15 02:49 UTC · model grok-4.3
The pith
Symmetric Boolean CSPs of arity at most 5 have their non-redundancy growth rates classified as O(n), O(n^2), or O(n^3), with all arity-4 cases and most arity-5 cases resolved.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
Our main result is a near-complete classification of the asymptotic growth of NRD_n(R) for symmetric Boolean predicates of arity at most 5. We resolve every predicate of arity at most 4 and all but two predicates of arity 5. For upper bounds we prove that t-balancedness is equivalent to the existence of degree-t multilinear polynomials capturing R and hence implies NRD_n(R)=O(n^t). For lower bounds we use the framework in which predicates that admit a special reduction from k-ary OR inherit the Omega(n^k) lower bound of OR.
What carries the argument
t-balancedness: the property that a symmetric Boolean relation R is captured by a multilinear polynomial of degree exactly t, which directly yields the upper bound NRD_n(R)=O(n^t).
If this is right
- Every t-balanced predicate satisfies NRD_n(R)=O(n^t).
- Any predicate that reduces from k-ary OR satisfies NRD_n(R)=Omega(n^k).
- The classification is complete for all symmetric Boolean predicates of arity <=4.
- The two remaining arity-5 predicates are reduced to concrete extremal set-system questions whose answers would finish the classification.
Where Pith is reading between the lines
- The same t-balancedness test may classify non-redundancy for symmetric predicates of arity 6 or 7 with only modest additional computation.
- Exact resolution of the two open arity-5 cases would link non-redundancy directly to the Erdős–Ko–Rado theorem or other intersecting-family bounds.
- Because non-redundancy controls kernel size and streaming complexity, the classification immediately yields tight kernelization and streaming results for the resolved predicates.
Load-bearing premise
The exhaustive computational enumeration has correctly identified every symmetric Boolean relation of arity at most 4 and all but two of arity 5, and the algebraic t-balancedness criteria are tight for the unresolved cases.
What would settle it
An explicit symmetric Boolean predicate of arity 5 whose largest non-redundant instance size is Theta(n^4) or whose size falls strictly between the Omega(n^2) and O(n^3) bounds currently claimed for the two open cases.
read the original abstract
Non-redundancy, introduced by Bessiere, Carbonnel, and Katsirelos (AAAI 2020), is a structural parameter for Constraint Satisfaction Problems ($\mathsf{CSPs}$) that governs kernelization, exact and approximate sparsification, and exact streaming complexity. It is the largest size of a $\mathsf{CSP}$ instance admitting no smaller subinstance with the same satisfying assignments. We study non-redundancy $\mathsf{NRD}_n(R)$ for Boolean symmetric $\mathsf{CSPs}$ defined by an $r$-ary relation $R$ whose value depends only on Hamming weight. An instance of $\mathsf{CSP}(R)$ has $n$ variables and constraints given by $r$-tuples; a constraint is satisfied exactly when the induced tuple lies in $R$. This class includes natural predicates such as cuts and $k$-SAT clauses. Our main result is a near-complete classification of the asymptotic growth of $\mathsf{NRD}_n(R)$ for symmetric Boolean predicates of arity at most $5$. Using computational experiments and algebraic upper- and lower-bound criteria, we resolve every predicate of arity at most $4$ and all but two predicates of arity $5$. For upper bounds, we introduce $t$-balancedness, a lifted, higher-degree version of the balancedness notion of Chen, Jansen, and Pieterse (Algorithmica 2020). We prove that $t$-balancedness is equivalent to the existence of degree-$t$ multilinear polynomials capturing $R$, and hence implies $\mathsf{NRD}_n(R)=O(n^t)$. For lower bounds, we use Carbonnel's (CP 2022) framework: predicates admitting a special reduction from $k$-ary OR inherit OR's lower bound $\Omega(n^k)$. The only unresolved arity-$5$ predicates in our framework have bounds $\Omega(n^2)$ and $O(n^3)$; we reduce their exact classification to natural extremal set-system questions.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies non-redundancy NRD_n(R) for symmetric Boolean CSP predicates R of arity at most 5. It claims a near-complete classification of the asymptotic growth of NRD_n(R), resolving every predicate of arity ≤4 and all but two of arity 5. Upper bounds follow from a new t-balancedness criterion shown equivalent to the existence of a degree-t multilinear polynomial capturing R (hence NRD_n(R)=O(n^t)); lower bounds follow from explicit reductions to the OR predicate (hence Ω(n^k) for suitable k). The two unresolved arity-5 cases are bounded by Ω(n²) from below and O(n³) from above and are reduced to open extremal set-system questions.
Significance. If the computational classification holds, the result is significant for the structural theory of CSPs: non-redundancy governs kernelization, sparsification, and streaming complexity, and a precise asymptotic map for all low-arity symmetric predicates supplies concrete, usable bounds for these applications. The algebraic equivalence between t-balancedness and polynomial capture, together with the parameter-free reductions from OR, supplies clean, independently checkable criteria; reducing the remaining cases to natural combinatorial questions is a further strength.
major comments (1)
- [Computational experiments] Computational experiments section: the central claim that every symmetric Boolean predicate of arity ≤4 and all but two of arity 5 has been correctly classified rests on an exhaustive enumeration over the 64 weight-based relations of arity 5 together with a search for the minimal t such that a degree-t multilinear polynomial captures R. No pseudocode, implementation details, or verification data for this search are supplied; an off-by-one error in the polynomial-degree test would misclassify the growth rate for one or more predicates and falsify the 'near-complete' statement.
minor comments (1)
- [Abstract] Abstract: the two unresolved arity-5 predicates are not identified and their concrete bounds (Ω(n²) lower, O(n³) upper) are not stated; adding this information would make the scope of the classification immediately clear.
Simulated Author's Rebuttal
We thank the referee for their careful reading and for the constructive comment on the computational experiments. We address the point below.
read point-by-point responses
-
Referee: [Computational experiments] Computational experiments section: the central claim that every symmetric Boolean predicate of arity ≤4 and all but two of arity 5 has been correctly classified rests on an exhaustive enumeration over the 64 weight-based relations of arity 5 together with a search for the minimal t such that a degree-t multilinear polynomial captures R. No pseudocode, implementation details, or verification data for this search are supplied; an off-by-one error in the polynomial-degree test would misclassify the growth rate for one or more predicates and falsify the 'near-complete' statement.
Authors: We agree that the computational experiments section lacks the requested implementation details, which is a genuine gap for reproducibility. In the revised manuscript we will add a new subsection (or appendix) containing: (i) pseudocode for the enumeration over all 64 subsets of allowed weights {0,…,5}; (ii) the exact linear-algebra procedure used to test, for each candidate t, whether a multilinear polynomial of degree at most t captures the predicate (solving the 32-equation system over the monomial coefficients with exact rational arithmetic); and (iii) a short verification note confirming that the minimal-t values obtained by the solver coincide with the t-balancedness criterion proved in the paper. For arity ≤4 the same procedure was cross-checked by hand on all 16 predicates. We will also state that the implementation is available upon request. This revision directly addresses the possibility of an off-by-one error. revision: yes
Circularity Check
No circularity in derivation chain
full rationale
The paper introduces t-balancedness as a new algebraic criterion, proves its equivalence to the existence of degree-t multilinear polynomials capturing the predicate R (yielding the O(n^t) upper bound), and obtains lower bounds via explicit reductions to the independently known OR predicate using Carbonnel's external framework. The classification for arities ≤4 (and most arity-5 cases) rests on exhaustive enumeration over the finite set of symmetric predicates defined by Hamming weights, which is a direct computational check against the algebraic criteria rather than any fitted parameter or self-referential equation. No load-bearing self-citations, ansatzes smuggled via prior work, or renamings of known results appear; the central claims remain independent of the paper's own outputs.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption Symmetric Boolean relations are those whose satisfaction depends only on the Hamming weight of the input tuple.
Reference graph
Works this paper leans on
-
[1]
arXiv:2604.01575 [cs]. Pre-published. [ABM12] Per Austrin, Siavosh Benabbas, and Avner Magen. “On quadratic threshold CSPs”. In:Discrete Mathematics & Theoretical Computer Science14.Discrete Algorithms (2012). [ACMM05] Amit Agarwal, Moses Charikar, Konstantin Makarychev, and Yury Makarychev. “O( p logn) approximation algorithms for Min UnCut, Min 2CNF Del...
-
[2]
Min-CSPs on Complete Instances II: Polylogarithmic Approximation for Min-NAE-3-SAT
Ed. by David Zuckerman. IEEE Computer Society, 2019, pp. 180–201.DOI: 10.1109/FOCS.2019.00021.URL:https://doi.org/10.1109/FOCS.2019.00021. [ALMS25] Aditya Anand, Euiwoong Lee, Davide Mazzali, and Amatya Sharma. “Min-CSPs on Complete Instances II: Polylogarithmic Approximation for Min-NAE-3-SAT”. In:Approximation, Random- ization, and Combinatorial Optimiz...
work page doi:10.1109/focs.2019.00021.url:https://doi.org/10.1109/focs.2019.00021 2019
-
[3]
LIPIcs. Schloss Dagstuhl — Leibniz- Zentrum f ¨ur Informatik, July 2022, 38:1–38:23.DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022
-
[4]
Classifying the complexity of constraints using finite algebras
[BJK05] Andrei Bulatov, Peter Jeavons, and Andrei Krokhin. “Classifying the complexity of constraints using finite algebras”. In:SIAM journal on computing34.3 (2005), pp. 720–742. [BZ20] Silvia Butti and Stanislav Zivny. “Sparsification of binary CSPs”. In:SIAM Journal on Discrete Mathematics34.1 (2020), pp. 825–842. [Car22] Cl´ement Carbonnel. “On redund...
-
[5]
Near-Optimal Space Lower Bounds for Streaming CSPs
arXiv:2604.01400 [cs]. Pre-published. [FV98] Tom´as Feder and Moshe Y Vardi. “The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory”. In:SIAM Journal on Computing28.1 (1998), pp. 57–104. [GL17] Venkatesan Guruswami and Euiwoong Lee. “Towards a characterization of approximation resistance ...
work page internal anchor Pith review Pith/arXiv arXiv 1998
-
[6]
Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph
LIPIcs. 2017, 11:1–11:27.DOI:10.4230/LIPICS.CCC.2017.11. [GVV17] Venkatesan Guruswami, Ameya Velingker, and Santhoshini Velusamy. “Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph”. In:Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. APPROX 2017 (Aug. 16–18, 2017). Ed. by Klaus Jansen, Jos ´e ...
-
[7]
Schloss Dagstuhl — Leibniz-Zentrum f ¨ur Informatik, Aug
LIPIcs. Schloss Dagstuhl — Leibniz-Zentrum f ¨ur Informatik, Aug. 2017, 8:1–8:19.DOI:
work page 2017
-
[8]
Some optimal inapproximability results
4230/LIPIcs.APPROX-RANDOM.2017.8. [H˚as01] Johan H˚astad. “Some optimal inapproximability results”. In:Journal of the ACM (JACM)48.4 (2001), pp. 798–859. [JCG97] Peter Jeavons, David Cohen, and Marc Gyssens. “Closure properties of constraints”. In:Journal of the ACM (JACM)44.4 (1997), pp. 527–548. [JP19] Bart MP Jansen and Astrid Pieterse. “Optimal sparsi...
work page 2017
-
[9]
[KK19] Michael Kapralov and Dmitry Krachun. “An Optimal Space Lower Bound for Approximating MAX-CUT”. In:Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. STOC (June 23–26, 2019). Association for Computing Machinery, June 2019, pp. 277–288.DOI: 10.1145/3313276.3316364. [KKMO07] Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan...
-
[10]
A Theory of Spectral CSP Sparsifica- tion
Ed. by David P . Woodruff. SIAM, 2024, pp. 5145–5168.DOI: 10.1137/1.9781611977912.185 .URL: https://doi.org/10.1137/1. 9781611977912.185. [KPS25a] Sanjeev Khanna, Aaron Putterman, and Madhu Sudan. “A Theory of Spectral CSP Sparsifica- tion”. In:arXiv preprint arXiv:2504.16206(2025). [KPS25b] Sanjeev Khanna, Aaron Putterman, and Madhu Sudan. “Efficient alg...
-
[11]
Linear time approximation schemes for the Gale- Berlekamp game and related minimization problems
LIPIcs. Schloss Dagstuhl– Leibniz-Zentrum f ¨ur Informatik, 2023, 80:1–80:15.DOI: 10.4230/LIPIcs.ITCS.2023.80.URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.80. [KS09] Marek Karpinski and Warren Schudy. “Linear time approximation schemes for the Gale- Berlekamp game and related minimization problems”. In:Proceedings of the forty...
-
[12]
Improved rounding techniques for the MAX 2-SAT and MAX DI-CUT problems
Ed. by David B. Shmoys. ACM, 2014, pp. 634–643.DOI: 10.1145/2591796. 2591817.URL:https://doi.org/10.1145/2591796.2591817. 25 [LLZ02] Michael Lewin, Dror Livnat, and Uri Zwick. “Improved rounding techniques for the MAX 2-SAT and MAX DI-CUT problems”. In:International Conference on Integer Programming and Combinatorial Optimization. Springer. 2002, pp. 67–8...
-
[13]
Optimal algorithms and inapproximability results for every CSP?
[Rag08] Prasad Raghavendra. “Optimal algorithms and inapproximability results for every CSP?” In: Proceedings of the fortieth annual ACM symposium on Theory of computing. 2008, pp. 245–254. [Sch78] Thomas J. Schaefer. “The Complexity of Satisfiability Problems”. In:Proceedings of the 10th ACM Symposium on Theory of Computing (STOC). ACM, 1978, pp. 216–226...
-
[14]
May 2023.DOI: 10.4230/ LIPIcs.APPROX/RANDOM.2023.15
LIPIcs. May 2023.DOI: 10.4230/ LIPIcs.APPROX/RANDOM.2023.15. [STV25] Noah G. Singer, Madhur Tulsiani, and Santhoshini Velusamy.Sketching Approximations and LP Approximations for Finite CSPs Are Related. Sept. 23,
work page 2023
-
[15]
Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
arXiv:2604.08731 [cs]. Pre-published. [SV26] Amatya Sharma and Santhoshini Velusamy.Characterizing Streaming Decidability of CSPs via Non-Redundancy
work page internal anchor Pith review Pith/arXiv arXiv
-
[16]
Characterizing Streaming Decidability of CSPs via Non-Redundancy
arXiv: 2604.21922 [cs.DS] .URL: https://arxiv.org/abs/2604. 21922. [Vu24] Hoa T Vu. “Revisiting maximum satisfiability and related problems in data streams”. In: Theoretical Computer Science982 (2024), p. 114271. [Zhu20] Dmitriy Zhuk. “A proof of the CSP dichotomy conjecture”. In:Journal of the ACM (JACM)67.5 (2020), pp. 1–78. 26
work page internal anchor Pith review Pith/arXiv arXiv 2024
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.