pith. sign in

arxiv: 2411.03451 · v2 · pith:SQWD43DWnew · submitted 2024-11-05 · 💻 cs.DS · cs.DM· cs.IT· cs.LO· math.CO· math.IT

Redundancy Is All You Need (for CSP Sparsification)

Joshua Brakensiek , Venkatesan Guruswami This is my paper

Pith reviewed 2026-05-23 17:27 UTC · model grok-4.3

classification 💻 cs.DS cs.DMcs.ITcs.LOmath.COmath.IT
keywords CSP sparsificationnon-redundancyconstraint satisfaction problemsentropy methodVC-type theoremset familiesnon-linear codes
0
0 comments X

The pith

For any CSP predicate, unweighted instances have sparsifiers of size at most their non-redundancy up to polylog factors.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that for any constraint satisfaction predicate R, redundant clauses in a CSP(R) instance suffice to produce a sparsifier whose size is bounded by the instance's non-redundancy. This bound holds up to polylogarithmic and 1/ε factors for unweighted instances and is determined by chain length for weighted ones. The argument proceeds by proving a VC-type theorem for multiplicative approximation that applies to arbitrary non-linear codes or set families. The proof applies the entropy method in a novel way to obtain the required approximation guarantee. As a direct consequence, prior non-redundancy results transfer to sparsification, and an explicit predicate is constructed whose non-redundancy has a fractional exponent between 1.5 and 1.6.

Core claim

For any CSP predicate R, every unweighted instance of CSP(R) has a sparsifier of size at most its non-redundancy (up to polylog and 1/ε factors). For weighted instances, sparsifiability is pinned to the chain length of the predicate. These results precisely determine the extent to which any CSP can be sparsified. The argument is carried out in the general setting of non-linear codes, or equivalently set families, by establishing a VC-type theorem for multiplicative error approximation via a novel application of the entropy method.

What carries the argument

Non-redundancy of a CSP instance, the maximum number of constraints such that each admits an assignment satisfying only that constraint, which serves as both the information-theoretic lower bound and the achievable sparsifier size upper bound.

If this is right

  • Existing non-redundancy bounds for CSP predicates immediately translate into sparsification guarantees for the same predicates.
  • Sparsifiability of weighted CSP instances is completely characterized by the chain length of the underlying predicate.
  • An explicit predicate exists whose non-redundancy lies between Ω(n^{1.5}) and Õ(n^{1.6}), giving the first proven non-integral exponent.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same entropy-method argument may extend to multiplicative sparsification questions for other set-system problems beyond CSPs.
  • Viewing hypergraph cuts or Abelian-group codes as special CSPs could yield new sparsifier constructions from the non-redundancy literature.
  • Further explicit predicates constructed via matching-vector techniques could exhibit additional non-integral non-redundancy exponents.

Load-bearing premise

The entropy method yields a VC-type theorem that supplies multiplicative approximation guarantees for general non-linear codes or set families.

What would settle it

A concrete CSP predicate R together with an unweighted instance whose smallest ε-sparsifier has size larger than the instance non-redundancy by more than a polylog( n / ε ) factor.

read the original abstract

The seminal work of Bencz\'ur and Karger demonstrated cut sparsifiers of near-linear size. Subsequent extensions have yielded sparsifiers for hypergraph cuts and more recently linear codes over Abelian groups. A decade ago, Kogan and Krauthgamer asked about the sparsifiability of arbitrary constraint satisfaction problems (CSPs). For this question, a trivial lower bound is the size of a non-redundant CSP instance, which admits, for each constraint, an assignment satisfying only that constraint (so that no constraint can be dropped by the sparsifier). For instance, for graph cuts, spanning trees are non-redundant instances. Our main result is that redundant clauses are sufficient for sparsification: for any CSP predicate R, every unweighted instance of CSP(R) has a sparsifier of size at most its non-redundancy (up to polylog and $1/\epsilon$ factors). For weighted instances, we similarly pin down the sparsifiability to the so-called chain length of the predicate. These results precisely determine the extent to which any CSP can be sparsified. Our result is established in the general setting of non-linear codes, or equivalently set families, yielding a VC-type theorem for multiplicative error approximation. A key technical ingredient in our work is a novel application of the entropy method from Gilmer's recent breakthrough on the union-closed sets conjecture. As an immediate consequence of our main theorem, a number of results in the non-redundancy literature immediately extend to CSP sparsification. We also contribute new techniques for understanding the non-redundancy of CSP predicates. By adapting methods from the matching vector codes literature in coding theory, we are able to construct an explicit predicate whose non-redundancy lies between $\Omega(n^{1.5})$ and $\widetilde{O}(n^{1.6})$, the first example with a provably non-integral exponent.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper claims that for any CSP predicate R, every unweighted CSP(R) instance admits a sparsifier whose size is at most the non-redundancy of the instance (up to polylog and 1/ε factors); for weighted instances, sparsifiability is determined by the chain length of R. This is obtained by proving a VC-type theorem for multiplicative (1±ε) approximation that holds in the general setting of non-linear codes (equivalently, arbitrary set families), via a novel application of Gilmer's entropy method originally developed for the union-closed sets conjecture. As a corollary, existing non-redundancy results extend to CSP sparsification, and the authors give an explicit predicate whose non-redundancy lies between Ω(n^{1.5}) and Õ(n^{1.6}).

Significance. If the central theorem holds, the work exactly characterizes the sparsifiability of arbitrary CSPs in terms of non-redundancy and chain length, answering the question posed by Kogan and Krauthgamer. The explicit non-integral-exponent construction via matching-vector-code techniques is a concrete advance in the non-redundancy literature. The entropy-method adaptation that yields a multiplicative VC theorem for general set families is a potentially reusable technical contribution.

major comments (2)
  1. [Main result and technical ingredient] Main result / technical ingredient section: the adaptation of Gilmer's entropy method must be shown to produce a bound that directly yields multiplicative (1±ε) concentration over all assignments for every predicate R. If the argument only recovers a combinatorial-dimension bound and then invokes a separate sampling lemma whose variance depends on predicate-specific properties, the claimed generality for arbitrary CSP(R) would not follow.
  2. [Main result] Theorem on weighted instances: the reduction from sparsifiability to chain length of the predicate should be stated with an explicit dependence on the chain length parameter; without this, it is unclear whether the polylog/ε factors remain independent of the predicate.
minor comments (2)
  1. [Abstract] Abstract: the phrase 'a number of results in the non-redundancy literature immediately extend' should list the specific prior theorems being invoked.
  2. [Introduction] The notation for non-redundancy and chain length should be introduced with a short formal definition in the introduction before being used in the main theorem statement.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive feedback. We address the two major comments point by point below.

read point-by-point responses

  1. Referee: [Main result and technical ingredient] Main result / technical ingredient section: the adaptation of Gilmer's entropy method must be shown to produce a bound that directly yields multiplicative (1±ε) concentration over all assignments for every predicate R. If the argument only recovers a combinatorial-dimension bound and then invokes a separate sampling lemma whose variance depends on predicate-specific properties, the claimed generality for arbitrary CSP(R) would not follow.

    Authors: The proof applies Gilmer's entropy method directly to arbitrary set families (equivalently, non-linear codes) to obtain a multiplicative (1±ε) concentration bound that holds uniformly over all assignments. The argument does not first recover only a combinatorial dimension and then appeal to a predicate-dependent sampling lemma; the entropy-based discrepancy bound itself guarantees the multiplicative approximation in the general setting. This is what enables the result for every CSP(R). We will add a short clarifying paragraph in the technical-ingredient section to make this direct applicability explicit. revision: partial

  2. Referee: [Main result] Theorem on weighted instances: the reduction from sparsifiability to chain length of the predicate should be stated with an explicit dependence on the chain length parameter; without this, it is unclear whether the polylog/ε factors remain independent of the predicate.

    Authors: We agree that an explicit statement improves clarity. The sparsifier size bound for weighted instances is O(ℓ(R) · non-redundancy · (log n)/ε²), where ℓ(R) is the chain length of the predicate and the polylog(n) and 1/ε factors are independent of any other property of R. We will revise the theorem statement (and the surrounding discussion) to display this dependence explicitly. revision: yes

Circularity Check

0 steps flagged

No significant circularity; main result is independent adaptation of external entropy method

full rationale

The paper derives its CSP sparsification bound (size at most non-redundancy up to polylog/ε) via a novel application of Gilmer's external entropy method to obtain a multiplicative VC-type theorem for non-linear codes/set families. This is an independent external citation (Gilmer's union-closed sets work), not a self-citation chain or self-definition. No equations reduce a prediction to a fitted input by construction, no uniqueness theorem is imported from the authors' prior work, and no ansatz is smuggled via citation. The derivation chain is self-contained against the external benchmark and does not collapse to its inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The proof rests on standard combinatorial axioms (entropy inequalities, VC-dimension properties) and the external Gilmer result; no data-fitted parameters or new postulated entities.

axioms (1)
  • standard math Entropy method yields multiplicative approximation bounds for set families (VC-type theorem)
    Invoked as key technical ingredient for the general non-linear code setting.

pith-pipeline@v0.9.0 · 5903 in / 1247 out tokens · 27946 ms · 2026-05-23T17:27:35.684912+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. An $\widetilde{O} (n^{3/7})$ Round Parallel Algorithm for Matroid Bases

    cs.DS 2026-05 unverdicted novelty 7.0

    A new algorithm finds a matroid basis in tilde O(n to the 3/7) adaptive rounds via independence oracle.

  2. Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa

    cs.DS 2025-07 unverdicted novelty 7.0

    Introduces strong sparsification for 1-in-3-SAT by merging variables, relying on a sub-quadratic vector-set bound derived from the Polynomial Freiman-Ruzsa Theorem, with an application to hypergraph coloring approximation.

Reference graph

Works this paper leans on

36 extracted references · 36 canonical work pages · cited by 2 Pith papers · 2 internal anchors

  1. [1]

    Woodruff, and Qin Zhang

    [ACK+16] Alexandr Andoni, Jiecao Chen, Robert Krauthgamer, Bo Qi n, David P. Woodruff, and Qin Zhang. On Sketching Quadratic Forms. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science , ITCS ’16, pages 311–319, New York, NY, USA, January

    work page 2016

  2. [2]

    An alyzing graph structure via linear measurements

    [AGM12a] Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. An alyzing graph structure via linear measurements. In Yuval Rabani, editor, Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012 , pages 459–467. SIAM,

    work page 2012

  3. [3]

    Improve d lower bound for frankl’s union- closed sets conjecture

    [AHS22] Ryan Alweiss, Brice Huang, and Mark Sellke. Improve d lower bound for frankl’s union- closed sets conjecture. arXiv preprint arXiv:2211.11731 ,

    work page arXiv

  4. [4]

    The johnson- lindenstrauss transform itself preserves differential priv acy

    [BBDS12] Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or S heffet. The johnson- lindenstrauss transform itself preserves differential priv acy. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science , pages 410–419. IEEE,

    work page 2012

  5. [5]

    New Lower Bounds for Matching Vector Codes

    [BDL13] Abhishek Bhowmick, Zeev Dvir, and Shachar Lovett. N ew Lower Bounds for Matching Vector Codes. (arXiv:1204.1367), March

    work page internal anchor Pith review Pith/arXiv arXiv

  6. [6]

    In Gary L

    time. In Gary L. Miller, editor, Proceedings of the Twenty-Eighth Annual ACM Sympo- sium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996 , pages 47–55. ACM,

    work page 1996

  7. [7]

    [Bop23] Ravi B. Boppana. A Useful Inequality for the Binary E ntropy Function. (arXiv:2301.09664), January

    work page arXiv

  8. [8]

    Better bounds for the union-closed se ts conjecture using the entropy approach

    [Cam22] Stijn Cambie. Better bounds for the union-closed se ts conjecture using the entropy approach. arXiv preprint arXiv:2212.12500 ,

    work page arXiv

  9. [9]

    On Redundancy in Constraint Sa tisfaction Problems

    [Car22] Cl´ ement Carbonnel. On Redundancy in Constraint Sa tisfaction Problems. In 28th International Conference on Principles and Practice of Constr aint Programming (CP 2022). Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik, 2022 . 58 [CD06] Charles J. Colbourn and Jeffrey H. Dinitz, editors. Handbook of Combinatorial Designs . Chapman and Hall/CRC,...

    work page 2022

  10. [10]

    Servedio

    [CDL+24] Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, and Roc co A. Servedio. Testing intersecting and union-closed families. In Venkatesan Gur uswami, editor, 15th Innova- tions in Theoretical Computer Science Conference, ITCS 2024, Janu ary 30 to February 2, 2024, Berkeley, CA, USA , volume 287 of LIPIcs, pages 33:1–33:23. Schloss Dagstuhl - Leibni...

    work page 2024

  11. [11]

    Liu, Richard Peng, Maximili an Probst Gutenberg, and Sushant Sachdeva

    [CKL+22] Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximili an Probst Gutenberg, and Sushant Sachdeva. Maximum flow and minimum-cost flow in al most-linear time. In 63rd IEEE Annual Symposium on Foundations of Computer Science , FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022 , pages 612–623. IEEE,

    work page 2022

  12. [12]

    [CKN20] Yu Chen, Sanjeev Khanna, and Ansh Nagda

    Association for Computing Machinery. [CKN20] Yu Chen, Sanjeev Khanna, and Ansh Nagda. Near-linea r Size Hypergraph Cut Spar- sifiers. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Sci ence (FOCS), pages 61–72, November

    work page 2020

  13. [13]

    Approximate union closed conjecture

    [CL22] Zachary Chase and Shachar Lovett. Approximate union closed conjecture. arXiv preprint arXiv:2211.11689,

    work page arXiv

  14. [14]

    Data-centric Graph Learning: A Survey

    [GBY+24] Yuxin Guo, Deyu Bo, Cheng Yang, Zhiyuan Lu, Zhongjian Zha ng, Jixi Liu, Yufei Peng, and Chuan Shi. Data-centric Graph Learning: A Survey. (arXi v:2310.04987), January

    work page arXiv

  15. [15]

    A constant lower bound for the union- closed sets conjecture

    [Gil22] Justin Gilmer. A constant lower bound for the union- closed sets conjecture. (arXiv:2211.09055), November

    work page arXiv

  16. [16]

    Ti me Complexity of Constraint Satisfaction via Universal Algebra

    [JLR17] Peter Jonsson, Victor Lagerkvist, and Biman Roy. Ti me Complexity of Constraint Satisfaction via Universal Algebra. LIPIcs, Volume 83, MFCS 2017 , 83:17:1–17:15,

    work page 2017

  17. [17]

    [JW20] Bart M. P. Jansen and Micha/suppress l W/suppress lodarczyk. Optimal polynomial-time compression for Boolean Max CSP. (arXiv:2002.03443), February

    work page arXiv 2002

  18. [18]

    [Kar93] David R. Karger. Global min-cuts in RNC, and other ra mifications of a simple min-cut algorithm. In Vijaya Ramachandran, editor, Proceedings of the Fourth An- nual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 25-27 Ja nuary 1993, Austin, Texas, USA , pages 21–30. ACM/SIAM,

    work page 1993

  19. [19]

    Hypergraph Tur´ an problems

    [Kee11] Peter Keevash. Hypergraph Tur´ an problems. In Robi n Chapman, editor, Surveys in Combinatorics 2011 , pages 83–140. Cambridge University Press, 1 edition, June

    work page 2011

  20. [20]

    Sketching Cuts in Graphs and Hypergraphs

    [KK15] Dmitry Kogan and Robert Krauthgamer. Sketching Cuts in Graphs and Hypergraphs. In Proceedings of the 2015 Conference on Innovations in Theoretic al Computer Sci- ence, ITCS ’15, pages 367–376, New York, NY, USA, January

    work page 2015

  21. [21]

    [KK23] Yotam Kenneth and Robert Krauthgamer

    As sociation for Computing Machinery. [KK23] Yotam Kenneth and Robert Krauthgamer. Cut sparsifica tion and succinct representa- tion of submodular hypergraphs. arXiv preprint arXiv:2307.09110 ,

    work page arXiv

  22. [22]

    Towards tight bounds for spectral sparsification of hypergraphs

    [KKTY21] Michael Kapralov, Robert Krauthgamer, Jakab Tard os, and Yuichi Yoshida. Towards tight bounds for spectral sparsification of hypergraphs. In Samir Khuller and Vir- ginia Vassilevska Williams, editors, STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021 , pages 598–611. ACM,

    work page 2021

  23. [23]

    Graph generated union-closed families of sets

    [Kni94] Emanuel Knill. Graph generated union-closed famil ies of sets. arXiv preprint math/9409215, 229,

    work page internal anchor Pith review Pith/arXiv arXiv

  24. [24]

    Putterman, and Madhu Suda n

    [KPS24a] Sanjeev Khanna, Aaron L. Putterman, and Madhu Suda n. Code Sparsification and its Applications. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , Proceedings, pages 5145–5168. Society for Industrial and Applied Mathematics, January

    work page 2024

  25. [25]

    Putterman, and Madhu Suda n

    [KPS24c] Sanjeev Khanna, Aaron L. Putterman, and Madhu Suda n. Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) , October

    work page 2024

  26. [26]

    [LLMV10] Arnaud Lallouet, Matthieu Lopez, Lionel Martin, a nd Christel Vrain

    ACM. [LLMV10] Arnaud Lallouet, Matthieu Lopez, Lionel Martin, a nd Christel Vrain. On Learning Con- straint Problems. In 2010 22nd IEEE International Conference on Tools with Artificia l Intelligence, volume 1, pages 45–52, October

    work page 2010

  27. [27]

    Path finding methods for linear programming: Solving linear programs in o (vrank) iterations and faster algorith ms for maximum flow

    [LS14] Yin Tat Lee and Aaron Sidford. Path finding methods for linear programming: Solving linear programs in o (vrank) iterations and faster algorith ms for maximum flow. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science , pages 424–433. IEEE,

    work page 2014

  28. [28]

    Automatic Design of Robot Behaviors through Constraint Network Acquisition

    [PBS08] Mathias Paulin, Christian Bessiere, and Jean Salla ntin. Automatic Design of Robot Behaviors through Constraint Network Acquisition. In 2008 20th IEEE International Conference on Tools with Artificial Intelligence , volume 1, pages 275–282, November

    work page 2008

  29. [29]

    Extension of a Method of Gilmer

    [Peb22] Luke Pebody. Extension of a Method of Gilmer. (arXiv :2211.13139), November

    work page arXiv

  30. [30]

    Quotient sparsification for submodul ar functions

    [Qua24] Kent Quanrud. Quotient sparsification for submodul ar functions. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , Proceedings, pages 5209–5248. Society for Industrial and Applied Mathem atics, January

    work page 2024

  31. [31]

    Decomposable submodular maximizatio n in federated setting

    [Raf24] Akbar Rafiey. Decomposable submodular maximizatio n in federated setting. arXiv preprint arXiv:2402.00138,

    work page arXiv

  32. [32]

    An improved lower bound for the union-cl osed set conjecture

    [Saw23] Will Sawin. An improved lower bound for the union-cl osed set conjecture. (arXiv:2211.11504), June

    work page arXiv

  33. [33]

    Mini-batch submodular maxim ization

    [Sch24] Gregory Schwartzman. Mini-batch submodular maxim ization. arXiv preprint arXiv:2401.12478,

    work page arXiv

  34. [34]

    Local graph sparsification for scalable clustering

    [SPR11] Venu Satuluri, Srinivasan Parthasarathy, and Yiye Ruan. Local graph sparsification for scalable clustering. In Timos K. Sellis, Ren´ ee J. Miller, Anastasios Kementsietsidis, and Yannis Velegrakis, editors, Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2011, Athens, Greece, June 12-1 6, 2011 , pages 721–732. ACM,

    work page 2011

  35. [35]

    Spielman and Shang-Hua Teng

    63 [ST04] Daniel A. Spielman and Shang-Hua Teng. Nearly-linea r time algorithms for graph partitioning, graph sparsification, and solving linear sys tems. In L´ aszl´ o Babai, editor, Proceedings of the 36th Annual ACM Symposium on Theory of Comput ing, Chicago, IL, USA, June 13-16, 2004 , pages 81–90. ACM,

    work page 2004

  36. [36]

    A Survey on Gr aph Neural Network Acceleration: Algorithms, Systems, and Customized Hardwa re

    [ZSW+23] Shichang Zhang, Atefeh Sohrabizadeh, Cheng Wan, Zijie H uang, Ziniu Hu, Yewen Wang, Yingyan, Lin, Jason Cong, and Yizhou Sun. A Survey on Gr aph Neural Network Acceleration: Algorithms, Systems, and Customized Hardwa re. (arXiv:2306.14052), June

    work page arXiv