pith. sign in

arxiv: 2606.18236 · v1 · pith:IQ6ZZSAInew · submitted 2026-06-16 · 💻 cs.LG · cs.IT· math.IT

Sign-Rank, Index, and List Replicability: Connections and Separations

Ari Blondal , Hamed Hatami , Pooya Hatami , Chavdar Lalov , Sivan Tretiak This is my paper

Pith reviewed 2026-06-27 01:39 UTC · model grok-4.3

classification 💻 cs.LG cs.ITmath.IT
keywords sign rankZ2-indexlist replicabilityconcept classesbinary classificationcombinatorial measureslearning theory
0
0 comments X

The pith

The Z2-index is upper-bounded by a linear function of the list replicability number for concept classes.

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

The paper orders two proposed lower bounds on the sign rank of binary concept classes. It proves that the Z2-index cannot exceed a constant multiple of the list replicability number. This ordering immediately yields a strong separation showing that sign rank can be arbitrarily larger than the Z2-index. The authors then develop direct upper bounds on list replicability itself using height and minimum star number, together with a composition theorem for products of classes.

Core claim

We show that the Z2-index is upper-bounded by a linear function of the list replicability number. As a main consequence we obtain a strong separation between sign rank and Z2-index. We establish upper bounds on the list replicability number by height and minimum star number, and prove that the list replicability number of the product of two concept classes is at most the sum of their individual list replicability numbers.

What carries the argument

The linear relation showing Z2-index is at most a constant times the list replicability number, which chains the two lower bounds on sign rank.

If this is right

  • Z2-index is at most linear in list replicability number.
  • Sign rank and Z2-index are separated by an arbitrary factor.
  • List replicability number is at most the height of the class.
  • List replicability number is at most the minimum star number.
  • List replicability number of a product class is at most the sum of the factors' numbers.

Where Pith is reading between the lines

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

  • Work on lower-bounding sign rank may shift focus from Z2-index to list replicability.
  • The composition result suggests list replicability behaves additively under independent combinations of features.

Load-bearing premise

The Z2-index and the list replicability number are both valid lower bounds on sign rank under the paper's definitions.

What would settle it

A concept class whose Z2-index exceeds every linear function of its list replicability number, or a class whose sign rank equals its Z2-index.

Figures

Figures reproduced from arXiv: 2606.18236 by Ari Blondal, Chavdar Lalov, Hamed Hatami, Pooya Hatami, Sivan Tretiak.

Figure 1
Figure 1. Figure 1: Two views of the simplicial complex ∆C for C = {++-, +++, +-+, --+, -++}. The following properties of ∆C are easy to deduce and can also be found in [CMW25, BHH+26b, FHV26]. • ∆C is a finite compact simplicial complex. • ∆C has vertex set contained in X × {±1} and is a subcomplex of the cross-polytope boundary ∆{±1}X . • Each maximal simplex of ∆C equals σc for some c ∈ C. • If C ± = C ∪ −C, then ∆C± is a … view at source ↗
read the original abstract

In learning theory, the sign rank of a binary concept class captures the smallest dimension in which it can be represented by points and halfspaces. Despite tremendous interest, lower bounds on sign rank are notoriously difficult to come by. Two recent approaches to the problem establish lower bounds on sign rank by measures that are easier to analyze: the $\mathbb{Z}_2$-index and the list replicability number. We order these measures, showing that the $\mathbb{Z}_2$-index is upper-bounded by a linear function of the list replicability number. As a main consequence, we obtain a strong separation between sign rank and $\mathbb{Z}_2$-index, thereby resolving a question of Frick, Hosseini, and Vasileuski. This motivates a thorough study of list replicability, the stronger of the two lower-bounding measures. We establish upper bounds on the list replicability number by two combinatorial measures: height and minimum star number. We also prove a fundamental composition result, showing that the product of two concept classes has list replicability number bounded by the sum of the list replicability numbers of the two classes.

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 connects sign-rank, the Z2-index, and the list replicability number for binary concept classes in learning theory. It proves that the Z2-index is at most linearly bounded by the list replicability number. As a consequence, it derives a strong separation between sign-rank and the Z2-index, resolving a question of Frick, Hosseini, and Vasileuski. It further establishes upper bounds on list replicability in terms of height and minimum star number, and proves a composition theorem bounding the list replicability of the product of two classes by the sum of their individual numbers.

Significance. If the ordering and separation hold, the work supplies a concrete tool for separating sign-rank from the Z2-index via an easier-to-analyze intermediate measure, addressing a known difficulty in obtaining sign-rank lower bounds. The composition result and the two combinatorial upper bounds on list replicability are useful for constructing and analyzing families of concept classes. The manuscript correctly attributes the lower-bound properties of both measures to prior work rather than re-deriving them.

major comments (2)
  1. [Abstract] The separation between sign-rank and Z2-index is obtained only if list replicability lower-bounds sign-rank under the definitions adopted in this manuscript (and likewise for the cited Z2-index lower bound). The paper should include an explicit statement or short appendix verifying that the formal definitions of both measures coincide with those in the two referenced recent approaches, or else cite the precise theorems that establish the lower bounds under the present notation.
  2. The composition theorem for the product of concept classes is load-bearing for the claim that list replicability is the stronger of the two measures. Without an explicit reference to the section containing its proof, it is impossible to check whether the sum bound is obtained by a direct product construction or requires additional assumptions on the classes.
minor comments (2)
  1. Notation for the list replicability number should be introduced once and used consistently; the abstract uses 'list replicability number' while later text may employ an abbreviation without prior definition.
  2. The manuscript would benefit from a short table comparing the three measures (sign-rank, Z2-index, list replicability) with respect to the new ordering and the two combinatorial upper bounds.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and helpful comments. We address each major comment below.

read point-by-point responses

  1. Referee: [Abstract] The separation between sign-rank and Z2-index is obtained only if list replicability lower-bounds sign-rank under the definitions adopted in this manuscript (and likewise for the cited Z2-index lower bound). The paper should include an explicit statement or short appendix verifying that the formal definitions of both measures coincide with those in the two referenced recent approaches, or else cite the precise theorems that establish the lower bounds under the present notation.

    Authors: We agree that an explicit verification strengthens the presentation. The formal definitions of sign-rank, Z2-index, and list replicability in the manuscript are identical to those in Frick, Hosseini, and Vasileuski (for Z2-index) and the referenced work establishing list-replicability lower bounds on sign-rank. We will add a short clarifying paragraph (with citations to the precise theorems establishing the lower bounds) immediately after the statement of the separation result in the introduction; a one-page appendix comparing notations can be included if the editor prefers. revision: yes

  2. Referee: The composition theorem for the product of concept classes is load-bearing for the claim that list replicability is the stronger of the two measures. Without an explicit reference to the section containing its proof, it is impossible to check whether the sum bound is obtained by a direct product construction or requires additional assumptions on the classes.

    Authors: The composition theorem is proved in Section 5 via a direct product construction that requires no additional assumptions on the classes beyond the standard definition of binary concept classes. We will insert an explicit forward reference to Section 5 both in the abstract and in the paragraph introducing the theorem in the main text. revision: yes

Circularity Check

0 steps flagged

No circularity in derivation chain

full rationale

The paper derives an ordering showing Z2-index is at most linear in list replicability number via direct combinatorial arguments on the measures, then obtains the sign-rank vs Z2-index separation as a consequence of this ordering combined with lower-bound claims attributed to two external recent approaches. No steps are self-definitional, no parameters are fitted and renamed as predictions, and the cited lower bounds are presented as independent prior results rather than self-citations whose authors overlap with the present work. The additional upper bounds on list replicability via height and star number, plus the composition theorem, are likewise established directly without reducing to the paper's own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work is purely combinatorial and relies on existing definitions of sign-rank, Z2-index, and list replicability from the cited literature; no new numerical parameters, invented entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)
  • domain assumption Z2-index and list replicability number are lower bounds on sign-rank (per the two recent approaches referenced)
    Invoked to justify using these measures for sign-rank lower bounds and to derive the separation.

pith-pipeline@v0.9.1-grok · 5751 in / 1276 out tokens · 37490 ms · 2026-06-27T01:39:45.078011+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

73 extracted references · 5 canonical work pages · 2 internal anchors

  1. [1]

    Advances in Neural Information Processing Systems , volume=

    Eluder dimension and the sample complexity of optimistic exploration , author=. Advances in Neural Information Processing Systems , volume=

  2. [2]

    Mahadev, N. V. R. and Peled, U. N. , TITLE =. 1995 , PAGES =

    1995

  3. [3]

    Nordic J

    Heggernes, Pinar and Kratsch, Dieter , TITLE =. Nordic J. Comput. , FJOURNAL =. 2007 , NUMBER =

    2007

  4. [4]

    Journal of Combinatorial Theory, Series A , volume=

    Kneser's conjecture, chromatic number, and homotopy , author=. Journal of Combinatorial Theory, Series A , volume=. 1978 , publisher=

    1978

  5. [5]

    Topological lower bounds for the chromatic number: A hierarchy

    Topological lower bounds for the chromatic number: A hierarchy , author=. arXiv preprint math/0208072 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  6. [6]

    Journal of Combinatorial Theory, Series A , volume=

    Box complexes, neighborhood complexes, and the chromatic number , author=. Journal of Combinatorial Theory, Series A , volume=. 2004 , publisher=

    2004

  7. [7]

    Local chromatic number,

    Simonyi, G. Local chromatic number,. Combinatorica , volume=. 2006 , publisher=

    2006

  8. [8]

    Transactions of the American Mathematical Society , volume=

    Local chromatic number and distinguishing the strength of topological obstructions , author=. Transactions of the American Mathematical Society , volume=

  9. [9]

    2002 , publisher=

    Algebraic Topology , author=. 2002 , publisher=

    2002

  10. [10]

    Using the

    Matoušek, Jiří , year=. Using the

  11. [11]

    2000 , publisher=

    Topology , author=. 2000 , publisher=

    2000

  12. [12]

    1987 , publisher=

    Real and complex analysis , author=. 1987 , publisher=

    1987

  13. [13]

    Florian Frick and Kaave Hosseini and Aliaksei Vasileuski , year=. A. 2604.01510 , archivePrefix=

    work page internal anchor Pith review Pith/arXiv arXiv

  14. [14]

    Approximation, Randomization, and Combinatorial Optimization

    Lower bound methods for sign-rank and their limitations , author=. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022) , pages=. 2022 , organization=

    2022

  15. [15]

    Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages =

    Ghazi, Badih and Golowich, Noah and Kumar, Ravi and Manurangsi, Pasin , title =. Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages =. 2021 , publisher =

    2021

  16. [16]

    Fan, Ky , TITLE =. Ann. of Math. (2) , FJOURNAL =. 1952 , PAGES =

    1952

  17. [17]

    Advances in Neural Information Processing Systems , volume=

    Unlabelled sample compression schemes for intersection-closed classes and extremal classes , author=. Advances in Neural Information Processing Systems , volume=

  18. [18]

    Ghazi, Badih and Kumar, Ravi and Manurangsi, Pasin , year =. User-. Advances in

  19. [19]

    An Equivalence Between Private Classification and Online Prediction , year=

    Bun, Mark and Livni, Roi and Moran, Shay , booktitle=. An Equivalence Between Private Classification and Online Prediction , year=

  20. [20]

    arXiv preprint arXiv:2212.05050 , year=

    The unstable formula theorem revisited via algorithms , author=. arXiv preprint arXiv:2212.05050 , year=

    work page arXiv

  21. [21]

    Proceedings of the 55th Annual ACM Symposium on Theory of Computing , series =

    Stability is stable: Connections between replicability, privacy, and adaptive generalization , author=. Proceedings of the 55th Annual ACM Symposium on Theory of Computing , series =. 2023 , pages=

    2023

  22. [22]

    Advances in Neural Information Processing Systems , volume=

    Replicability in reinforcement learning , author=. Advances in Neural Information Processing Systems , volume=

  23. [23]

    The Eleventh International Conference on Learning Representations , year=

    Replicable Bandits , author=. The Eleventh International Conference on Learning Representations , year=

  24. [24]

    Replicable Clustering , volume =

    Esfandiari, Hossein and Karbasi, Amin and Mirrokni, Vahab and Velegkas, Grigoris and Zhou, Felix , booktitle =. Replicable Clustering , volume =

  25. [25]

    Advances in Neural Information Processing Systems , volume=

    The bayesian stability zoo , author=. Advances in Neural Information Processing Systems , volume=

  26. [26]

    Advances in Neural Information Processing Systems , volume=

    Understanding the eluder dimension , author=. Advances in Neural Information Processing Systems , volume=

  27. [27]

    Discrete Mathematics , volume=

    Classes of graphs without star forests and related graphs , author=. Discrete Mathematics , volume=. 2022 , publisher=

    2022

  28. [28]

    The Journal of Machine Learning Research , volume=

    Minimax analysis of active learning , author=. The Journal of Machine Learning Research , volume=. 2015 , publisher=

    2015

  29. [29]

    Proceedings of the 37th International Conference on Neural Information Processing Systems , articleno =

    Eaton, Eric and Hussing, Marcel and Kearns, Michael and Sorrell, Jessica , title =. Proceedings of the 37th International Conference on Neural Information Processing Systems , articleno =. 2023 , publisher =

    2023

  30. [30]

    Proceedings of the 41st International Conference on Machine Learning , articleno =

    Kalavasis, Alkis and Karbasi, Amin and Larsen, Kasper Green and Velegkas, Grigoris and Zhou, Felix , title =. Proceedings of the 41st International Conference on Machine Learning , articleno =. 2024 , publisher =

    2024

  31. [31]

    Commentarii Mathematici Helvetici , volume=

    Levels in algebra and topology , author=. Commentarii Mathematici Helvetici , volume=. 1984 , publisher=

    1984

  32. [32]

    Commentarii Mathematici Helvetici , volume=

    The level of real projective spaces , author=. Commentarii Mathematici Helvetici , volume=. 1989 , publisher=

    1989

  33. [33]

    Mathematische Annalen , author =

    Smooth equivariant triangulations of. Mathematische Annalen , author =. 1978 , pages =

    1978

  34. [34]

    Geometrical Realization of Set Systems and Probabilistic Communication Complexity , booktitle =

    Noga Alon and Peter Frankl and Vojtech R. Geometrical Realization of Set Systems and Probabilistic Communication Complexity , booktitle =

  35. [35]

    International Conference on Algorithmic Learning Theory , pages=

    Labeled compression schemes for extremal classes , author=. International Conference on Algorithmic Learning Theory , pages=. 2016 , organization=

    2016

  36. [36]

    Journal of Computer and System Sciences , volume=

    Probabilistic communication complexity , author=. Journal of Computer and System Sciences , volume=. 1986 , publisher=

    1986

  37. [37]

    Sur l'homologie des vari\'

    Thom, Ren\'. Sur l'homologie des vari\'. Differential and. 1965 , MRCLASS =

    1965

  38. [38]

    , TITLE =

    Warren, Hugh E. , TITLE =. Trans. Amer. Math. Soc. , FJOURNAL =. 1968 , PAGES =

    1968

  39. [39]

    , TITLE =

    Milnor, J. , TITLE =. Proc. Amer. Math. Soc. , FJOURNAL =. 1964 , PAGES =

    1964

  40. [40]

    A linear lower bound on the unbounded error probabilistic communication complexity , NOTE =

    Forster, J\". A linear lower bound on the unbounded error probabilistic communication complexity , NOTE =. J. Comput. System Sci. , FJOURNAL =. 2002 , NUMBER =

    2002

  41. [41]

    Sign rank versus

    Alon, Noga and Moran, Shay and Yehudayoff, Amir , booktitle=. Sign rank versus. 2016 , organization=

    2016

  42. [42]

    Alon, Noga and Bun, Mark and Livni, Roi and Malliaris, Maryanthe and Moran, Shay , TITLE =. J. ACM , FJOURNAL =. 2022 , NUMBER =

    2022

  43. [43]

    A theory of

    Alon, Noga and Hanneke, Steve and Holzman, Ron and Moran, Shay , booktitle=. A theory of. 2021 , organization=

    2021

  44. [44]

    The Thirty Seventh Annual Conference on Learning Theory , pages=

    The star number and eluder dimension: Elementary observations about the dimensions of disagreement , author=. The Thirty Seventh Annual Conference on Learning Theory , pages=. 2024 , organization=

    2024

  45. [45]

    2025 , booktitle =

    Ari Blondal and Shan Gao and Hamed Hatami and Pooya Hatami , title =. 2025 , booktitle =

    2025

  46. [46]

    2503.15294 , archivePrefix=

    Ari Blondal and Hamed Hatami and Pooya Hatami and Chavdar Lalov and Sivan Tretiak , year=. 2503.15294 , archivePrefix=

    work page arXiv

  47. [47]

    Blondal, Ari and Hatami, Hamed and Hatami, Pooya and Lalov, Chavdar and Tretiak, Sivan , booktitle=. Borsuk-

  48. [48]

    17th Innovations in Theoretical Computer Science Conference (ITCS 2026) , pages =

    Blondal, Ari and Hatami, Hamed and Hatami, Pooya and Lalov, Chavdar and Tretiak, Sivan , title =. 17th Innovations in Theoretical Computer Science Conference (ITCS 2026) , pages =. 2026 , volume =

    2026

  49. [49]

    2026 , eprint=

    Tight list replicability bounds via a novel sphere covering theorem , author=. 2026 , eprint=

    2026

  50. [50]

    2023 , volume =

    Chase, Zachary and Moran, Shay and Yehudayoff, Amir , booktitle =. 2023 , volume =

    2023

  51. [51]

    Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages =

    Chase, Zachary and Chornomaz, Bogdan and Moran, Shay and Yehudayoff, Amir , title =. Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages =. 2024 , isbn =

    2024

  52. [52]

    Proceedings of Thirty Eighth Conference on Learning Theory , pages =

    Spherical Dimension , author =. Proceedings of Thirty Eighth Conference on Learning Theory , pages =. 2025 , editor =

    2025

  53. [53]

    and Vander Woude, Jason and Vinodchandran, N

    Dixon, Peter and Pavan, A. and Vander Woude, Jason and Vinodchandran, N. V. , title =. Proceedings of the 37th International Conference on Neural Information Processing Systems , articleno =. 2023 , publisher =

    2023

  54. [54]

    Forty-second International Conference on Machine Learning , year=

    The Role of Randomness in Stability , author=. Forty-second International Conference on Machine Learning , year=

  55. [55]

    Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages =

    Impagliazzo, Russell and Lei, Rex and Pitassi, Toniann and Sorrell, Jessica , title =. Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages =. 2022 , isbn =

    2022

  56. [56]

    The Thirty Seventh Annual Conference on Learning Theory , pages=

    Dual VC dimension obstructs sample compression by embeddings , author=. The Thirty Seventh Annual Conference on Learning Theory , pages=. 2024 , organization=

    2024

  57. [57]

    Proceedings of the 40th International Conference on Machine Learning , articleno =

    Kalavasis, Alkis and Karbasi, Amin and Moran, Shay and Velegkas, Grigoris , title =. Proceedings of the 40th International Conference on Machine Learning , articleno =. 2023 , publisher =

    2023

  58. [58]

    Patterns , author =

    Leakage and the reproducibility crisis in machine-learning-based science , issn =. Patterns , author =. 2023 , note =

    2023

  59. [59]

    and Pitts, Walter , TITLE =

    McCulloch, Warren S. and Pitts, Walter , TITLE =. Bull. Math. Biophys. , FJOURNAL =. 1943 , PAGES =

    1943

  60. [60]

    , author=

    The perceptron: a probabilistic model for information storage and organization in the brain. , author=. Psychological Review , volume=. 1958 , publisher=

    1958

  61. [61]

    2014 , isbn =

    Shalev-Shwartz, Shai and Ben-David, Shai , title =. 2014 , isbn =

    2014

  62. [62]

    and Radcliffe, Jamie and Vinodchandran, N

    Vander Woude, Jason and Dixon, Peter and Pavan, A. and Radcliffe, Jamie and Vinodchandran, N. V. , booktitle =. Replicability in Learning: Geometric Partitions and KKM-Sperner Lemma , volume =. doi:10.52202/079017-2508 , editor =

    work page doi:10.52202/079017-2508

  63. [63]

    Machine Learning , volume=

    Learning nested differences of intersection-closed concept classes , author=. Machine Learning , volume=. 1990 , publisher=

    1990

  64. [64]

    Information and Computation , volume=

    Predicting \ 0, 1 \ -functions on randomly drawn points , author=. Information and Computation , volume=. 1994 , publisher=

    1994

  65. [65]

    Sample compression, learnability, and the

    Floyd, Sally and Warmuth, Manfred , journal=. Sample compression, learnability, and the. 1995 , publisher=

    1995

  66. [66]

    Self-directed learning and its relation to the

    Ben-David, Shai and Eiron, Nadav , journal=. Self-directed learning and its relation to the. 1998 , publisher=

    1998

  67. [67]

    European Conference on Computational Learning Theory , pages=

    On teaching and learning intersection-closed concept classes , author=. European Conference on Computational Learning Theory , pages=. 1999 , organization=

    1999

  68. [68]

    Theoretical Computer Science , volume=

    Learnability of quantified formulas , author=. Theoretical Computer Science , volume=. 2003 , publisher=

    2003

  69. [69]

    Auer, Peter and Ortner, Ronald , journal=. A new. 2007 , publisher=

    2007

  70. [70]

    Information Processing Letters , volume=

    The optimal PAC bound for intersection-closed concept classes , author=. Information Processing Letters , volume=. 2015 , publisher=

    2015

  71. [71]

    Journal of Machine Learning Research , volume=

    Refined error bounds for several learning algorithms , author=. Journal of Machine Learning Research , volume=

  72. [72]

    Conference on Learning Theory , pages=

    Robust learning under clean-label attack , author=. Conference on Learning Theory , pages=. 2021 , organization=

    2021

  73. [73]

    Journal of Computer and System Sciences , volume=

    Unlabeled sample compression schemes and corner peelings for ample and maximum classes , author=. Journal of Computer and System Sciences , volume=. 2022 , publisher=

    2022