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

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

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

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

machine learning, deep learning, neural networks

Sign-Rank, Index, and List Replicability: Connections and Separations Ari Blondal∗

Hamed Hatami∗

Pooya Hatami †

Chavdar Lalov†

Sivan Tretiak†

arXiv:2606.18236v1 [cs.LG] 16 Jun 2026

April 2026

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 Z2 -index and the list replicability number. We order these measures, showing 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, 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.

Contents 1 Introduction 1.1 Our results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.1 List replicability bridges Z2 -index and sign-rank. . . . . . . . . . . . . . . . . . . . . . 1.1.2 Extremal classes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.3 Height and eluder dimension. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.4 The star number. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.5 Separation of coindex and list replicability for partial classes. . . . . . . . . . . . . . . 1.1.6 List replicability under joins and concatenations. . . . . . . . . . . . . . . . . . . . . . 1.2 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Concluding remarks and open problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Technical overview of Theorem 1.1 and Theorem 1.2 . . . . . . . . . . . . . . . . . . . . . . .

2 3 3 4 4 5 7 7 8 9 11

2 Preliminaries 12 2.1 The Z2 -topological framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.2 The Z2 -index of sign matrices and concept classes . . . . . . . . . . . . . . . . . . . . . . . . 13 2.3 List replicability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3 Separating sign-rank and index 15 3.1 List replicability number upper bounds index . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.2 A list-replicable algorithm for PG(2, q) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 ∗ McGill University, [email protected], [email protected]. Ari Blondal and Hamed Hatami are supported by NSERC grants. † Ohio State University, {hatami.2, lalov.1, tretiak.2}@osu.edu

4 A height-based list replicability algorithm

5 Height and eluder dimension

6 Separation of coindex and list replicability

7 Composition properties for list replicability

Introduction

In this paper, we study sign matrices and finite concept classes via three complementary notions of complexity: a geometric notion (sign-rank), a topological notion (Z2 -index), and an algorithmic learning-theoretic notion (list replicability). We show that list replicability number lies between Z2 -index and sign-rank, and use this to obtain a strong separation between Z2 -index and sign-rank. We also show that several existing Z2 -index upper bounds in fact hold at the stronger level for list replicability, and develop new upper bounds, lower bounds, and closure properties for list replicability itself. Sign-rank. Sign-rank is a fundamental and well-studied parameter in learning theory which captures the smallest dimension in which a binary classification problem admits a linear representation. Formally, the sign-rank of a matrix A with entries in {+1, −1} is the minimum rank of a real matrix B with sign(Bi,j ) = Ai,j for all entries i, j. Given a binary concept class C ⊆ {±1}X over a finite domain X , the sign-rank signrk(C) is the sign-rank of the |C| × |X | matrix A defined by Ac,x = c(x). Equivalently, it is the smallest d for which there exist embeddings {uc ∈ Rd }c∈C and {vx ∈ Rd }x∈X satisfying c(x) = sign ⟨uc , vx ⟩

for all c ∈ C, x ∈ X .

(1)

Classical results on sign patterns of polynomials imply that most N × N sign matrices have sign-rank Ω(N ) [AMY16, Lemma 22]. Nevertheless, proving even super-constant lower bounds for well-structured matrices that lack pseudorandom properties has remained elusive [HHP+ 22]. A promising new approach was recently proposed by Frick, Hosseini, and Vasileuski [FHV26], who developed a topological framework for sign-rank lower bounds based on the Z2 -index of a space associated with the sign matrix. We now describe this framework. The Z2 -index of a concept class. A distribution µ over X × {±1} is realizable by a concept c ∈ C if every pair (x, b) in its support satisfies b = c(x). Given C, let C ± := C ∪ {−c : c ∈ C} denote its antipodal completion, and let ∆C ± be the set of all distributions realizable by some c ∈ C ± . Equipped with the total variation metric, ∆C ± becomes a topological space. Recall that a Z2 -action on a topological space X is a continuous involution τ : X → X (i.e., τ ◦ τ = id); it is free if τ has no fixed points. The two examples relevant to us are: • The space ∆C ± with the label-negation action µ 7→ −µ, where (−µ)(x, b) := µ(x, −b). • The unit sphere Sd ⊂ Rd+1 with the antipodal action x 7→ −x. Let X be a topological space with a free Z2 -action τ . A continuous map Φ : X → Sd is Z2 -equivariant if it preserves the Z2 -action: Φ(τ (x)) = −Φ(x) for all x ∈ X. The Z2 -index of X is IndZ2 (X) := min d : there exists a Z2 -equivariant map X → Sd . In particular, IndZ2 (Sn ) = n; this is in fact equivalent to the Borsuk–Ulam theorem. Frick et al. [FHV26] defined the Z2 -index of a concept class C as IndZ2 (C) := IndZ2 (∆C ± ), where ∆C ± is equipped with the label-negation Z2 -action described above. 2

Dual to the Z2 -index is the Z2 -coindex of a concept class C, which is the dual invariant obtained by reversing the direction of the equivariant map. Namely, coIndZ2 (C) is the largest d for which there is a Z2 -equivariant map Sd → ∆C ± . The Z2 -coindex was previously studied under the name spherical dimension in [CMW25]. Note that, by the Borsuk–Ulam theorem, coIndZ2 (C) ≤ IndZ2 (C). Connection to sign-rank. As observed in [FHV26], the sign-rank decomposition (1) naturally produces a Z2 -equivariant map from ∆C ± to Sd−1 : Suppose signrk(C) ≤ d, with embeddings {uc }c∈C and {vx }x∈X as in (1). The antipodal completion does not increase sign-rank, since we may set u−c := −uc . The domain embedding x 7→ vx extends by linearity to a map ψ : ∆C ± → Rd , defined as ψ(µ) := E(x,b)∼µ [b vx ]. If µ is realizable by c ∈ C ± , then every (x, b) ∼ µ satisfies ⟨uc , bvx ⟩ = |⟨uc , vx ⟩| > 0 with probability 1, and therefore, ψ(µ) ̸= 0. Hence, we can normalize Φ(µ) := ψ(µ)/ ||ψ(µ)|| to obtain a continuous map Φ : ∆C ± → Sd−1 . Since ψ is linear and label-negation reverses the signed weights, ψ(−µ) = −ψ(µ), and hence Φ(−µ) = −Φ(µ), i.e., Φ is Z2 -equivariant. Therefore, IndZ2 (C) ≤ signrk(C) − 1. (2) In light of the construction above, the Z2 -index can be viewed as a topological relaxation of sign-rank: while sign-rank requires the map ψ from realizable distributions to Rd \ {0} to be linear, the Z2 -index asks only for a continuous Z2 -equivariant map with no linearity requirement. List replicability. There are various formalizations of replicability in learning theory, most of which build off of the well-established notion of probably approximately correct (PAC) learning. An (ϵ, δ)-PAC learning algorithm for a concept class C receives n := nC (ϵ, δ) i.i.d. examples from an unknown realizable distribution µ and, with probability at least 1 − δ, produces a hypothesis h : X → {±1} with population loss lossµ (h) := P(x,b)∼µ [h(x) ̸= b] ≤ ϵ. Given L ∈ N, such an algorithm is L-list-replicable if for every realizable distribution µ ∈ ∆C , the output hypothesis belongs to a small list Lµ = {h1 , . . . , hL } with probability at least 1 − δ. The list may depend on µ, but its size must not. The list replicability number lr(C), introduced by [CMY23, DPVWV23], is the smallest L for which an L-list-replicable (ϵ, δ)-PAC learner exists for all ϵ, δ > 0.

1.1

Our results

1.1.1

List replicability bridges Z2 -index and sign-rank.

Our main result connects the Z2 -index to list replicability. Theorem 1.1 (Index is controlled by list replicability). For every concept class C ⊆ {±1}X over a finite domain X , IndZ2 (C) ≤ 2 lr(C) − 1. It is shown in [BHH+ 26a] that, over finite domains, lr(C) ≤ signrk(C). Combining this with Theorem 1.1 and the Borsuk–Ulam inequality coIndZ2 (C) ≤ IndZ2 (C) gives the following chain of inequalities: 1 1 coIndZ2 (C) ≤ IndZ2 (C) < lr(C) ≤ signrk(C). 2 2

(3)

Frick et al. [FHV26, Question 7] asked whether there exists a function f such that signrk(C) ≤ f (IndZ2 (C)) for every finite concept class C. We use Theorem 1.1 in conjunction with existing results about sign-rank to show that no such bound exists. 3

Theorem 1.2 (Sign-rank is not bounded by index). There exists a family of N × N sign matrices whose Z2 -index is at most 5, while their sign-rank grows polynomially in N . The matrices are incidence matrices of finite projective planes. Their sign-rank is known to be polynomially large by the lower bound of Alon, Moran, and Yehudayoff [AMY16]. We show in Theorem 3.2 that their list replicability number is at most 3. Theorem 1.1 then gives IndZ2 ≤ 5. 1.1.2

Extremal classes.

Recall that a set S ⊆ X is shattered by C ⊆ {±1}X if C|S = {±1}S , and the VC dimension of C is the size of the largest set that it shatters. An immediate topological ramification of shattering a set S of size d is that the set of distributions in ∆C ± supported on S is homeomorphic to Sd−1 (via the identification of distributions with ℓ1 -unit vectors in RX ), and therefore coIndZ2 (C) ≥ d − 1. Consequently, every concept class satisfies vc(C) − 1 ≤ coIndZ2 (C) ≤ IndZ2 (C). A set S ⊆ X is strongly shattered by E ⊆ {±1}X if there is a fixed labelling a ∈ {±1}X \S with {c|S : c ∈ E, c|X \S = a} = {±1}S . A class E is extremal if every shattered set is also strongly shattered. Many natural concept classes are extremal or admit natural extremal extensions; see [CCMW22, Section 3.2] for a list of examples. Extremal classes are among the few cases where list replicability is well understood. Blondal et al. [BHH+ 26b] showed that for an extremal class E ⊆ {±1}X over a finite domain, ( vc(E) if E = {±1}X , (4) lr(E) = vc(E) + 1 otherwise. Combined with Theorem 1.1 and the general bound coIndZ2 (C) ≥ vc(C) − 1, this pins down all three parameters up to a factor of two: for every extremal class E, vc(E) − 1 ≤ coIndZ2 (E) ≤ IndZ2 (E) ≤ 2 lr(E) − 1 ≤ 2 vc(E) + 1. 1.1.3

(5)

Height and eluder dimension.

Invariants which capture a notion of height for topological spaces (such at the Stiefel–Whitney height) are standard tools for bounding the Z2 -index/coindex. In the same vein, Frick et al. [FHV26] introduced a combinatorial notion of height as a way to upper-bound the Z2 -index of a sign matrix. Using this approach, they showed that random N × N sign matrices and the Hadamard matrix have Z2 -index O(log N ). We instead use a version of their height definition adapted to partial concept classes C ⊆ {±1, ⋆}X (both versions are equivalent up to a constant factor). For two partial concepts h1 , h2 ∈ {±1, ⋆}X , define their junction by ( h1 (x) if h1 (x) = h2 (x), (h1 ∩ h2 )(x) = ⋆ otherwise. We write g ⪯ h if g = g ∩ h. Write g ≺ h if g ⪯ h and g ̸= h. Define the junction closure of a partial concept class C ⊆ {±1, ⋆}X as, ( ) \ J (C) = c : ∅ ̸= S ⊆ C c∈S

The height of C, denoted H(C), is the length m of the longest strict chain h1 ≺ h2 ≺ · · · ≺ hm in J (C).1 1 Given C ⊆ {±1}X , let S := {c+ , c− : c ∈ C}, where c+ := {x : c(x) = 1} and c− := {x : c(x) = −1}, and let I be the C C set of all finite non-empty intersections of elements of SC . Frick et al. [FHV26] define the height hFHV (C) as the length of the longest strict chain in IC . Up to the convention of whether the empty set is included in IC ,

hFHV (C) ≤ H(C ± ) ≤ 2 hFHV (C) − 1.

In view of the aforementioned bound of Frick et al. on the Z2 -index by height, and our Theorem 1.1 bounding the Z2 -index by lr, it is natural to ask how the two upper-bounding quantities, height and lr, compare. Our next result clarifies this by showing that height also upper-bounds lr. Theorem 1.3 (Height controls list replicability). For every finite partial concept class C ⊆ {±1, ⋆}X , lr(C) ≤ H(C). The proof of Theorem 1.3, as found in Section 4, is algorithmic. We construct a learner whose output hypothesis is likely to lie on a single chain in the junction closure of the class. Since every such chain has length at most H(C), the learner is H(C)-list-replicable. The combinatorial notion of height given by H(C) has a useful equivalence to a learning-theoretic parameter known as eluder dimension. The eluder dimension was introduced by Russo and Van Roy [RVR13] as a sequential notion of independence for function classes. Informally, it is the maximum length of a sequence of points such that, at each step, the label at the next point is not determined by the labels on the preceding points. Fix a finite partial concept class C ⊆ {±1, ⋆}X and a base concept c′ ∈ C. Write supp(c′ ) := {x ∈ X : ′ c (x) ̸= ⋆}. The eluder dimension of C relative to c′ , denoted Edim(C, c′ ), is the largest m for which there exist points x1 , . . . , xm ∈ supp(c′ ) and concepts c1 , . . . , cm ∈ C such that, for every i ∈ [m], ci (xi ) ̸= c′ (xi ), (ci (xi ) = ⋆ allowed) while at every earlier position j < i, ci (xj ) = c′ (xj ). The eluder dimension of C is Edim(C) := supc′ ∈C Edim(C, c′ ). Proposition 1.4 (Height and eluder dimension are equivalent). For any finite partial concept class C ⊆ {±1, ⋆}X , H(C) = Edim(C) + 1. We prove a slightly stronger form of this in Proposition 5.3. The result allows us to translate the bound lr(C) ≤ H(C) into the existing literature surrounding eluder dimension, as will be seen in the following section. 1.1.4

The star number.

The star number is a classical combinatorial parameter from learning theory that measures the size of the largest local star around a target labelling [HY15]. Definition 1.5 (Star number). For a class C ⊆ {±1}X and a center h ∈ {±1}X , let sh (C) denote the largest m for which there exist distinct points x1 , . . . , xm ∈ X and concepts c0 , c1 , . . . , cm ∈ C such that ⇐⇒

ci (xj ) = h(xj )

i ̸= j

for every i ∈ {0, . . . , m} and j ∈ [m]. Thus c0 agrees with h on all of x1 , . . . , xm , while each other ci disagrees with h exactly at xi . We consider both extremes over the choice of center: smin (C) :=

min

h∈{±1}X

sh (C)

and

smax (C) :=

max sh (C).

h∈{±1}X

Hanneke [Han24] showed that the star number characterizes intersection-closed structure: the minimum star number smin (C) of a concept class C equals the least possible VC dimension of a generalized intersectionclosed class H containing C. 5

Definition 1.6 (Generalized intersection-closed). We say that H ⊆ {±1}X is generalized intersection-closed if there exists a center h⋆ ∈ {±1}X such that, for every nonempty finite A ⊆ H, the concept ! ( ^ h⋆ (x), if c(x) = h⋆ (x) for every c ∈ A, A (x) := −h⋆ (x), otherwise h ⋆

also belongs to H. This notion generalizes the classical definition of an intersection-closed class, which corresponds to the case where h⋆ is the all-1 hypothesis. We show that all finite concept classes can be list-replicably learned with list size O(smin ), by combining Hanneke’s characterization with known embeddings into extremal concept classes. Theorem 1.7. For every finite binary concept class C ⊆ {±1}X , lr(C) ≤ 11smin (C) + 1. Proof. By Hanneke’s characterization of intersection-closed classes, C embeds into a generalized intersectionclosed class H satisfying vc(H) = smin (C); see [Han24, Theorem 19 and Remark 24]. Rubinstein and Rubinstein show that every generalized intersection-closed class of VC dimension d embeds into an extremal class of VC dimension at most 11d; see [RR22, Theorems 4.1 and 4.4]. Applying this result to H, we obtain an extremal class E ⊆ {±1}X such that C ⊆ H ⊆ E and vc(E) ≤ 11 vc(H) = 11smin (C). This combined embedding statement is also recorded explicitly in [Han24, Corollary 27]. Finally, by Equation (4), every finite extremal class satisfies lr(E) ≤ vc(E) + 1. By monotonicity of the list replicability under taking subclasses, we conclude lr(C) ≤ lr(E) ≤ vc(E) + 1 ≤ 11smin (C) + 1. Remark 1.8. It is easy to see that the maximum star number is upper bounded by eluder dimension and height2 . In particular, for every concept class C, we have smin (C) ≤ smax (C) ≤ Edim(C) = H(C) − 1.

(6)

Thus, for total classes, Theorem 1.7 is a strengthening, ignoring constant factors, of the height/eluder bound lr(C) ≤ H(C) of Theorem 1.3. The height bound, however, applies in the more general setting of partial concept classes. Star number and sign-rank Li, Kamath, Foster, and Srebro [LKFS22] asked whether there exist concept classes with bounded smax but arbitrarily large sign-rank. They also conjectured the stronger statement that there exist concept classes with constant Edim and arbitrarily large sign rank. We disprove both of these conjectures: sign-rank is bounded by a function of smax alone. 2 In fact, Li, Kamath, Foster, and Srebro [LKFS22] showed that the eluder dimension is characterized by the maximum of star number and threshold dimension: max{smax (C), Tdim(C)} ≤ Edim(C) ≤ 4max{smax (C),Tdim(C)} .

Theorem 1.9. For every sign matrix A with smax (A) ≤ d, 2 4d

signrk(A) ≤ 2 f (d)2 ≤ 2 (2d2 )2(2d ) , where f is the function from [Atm22, Theorem 2.1]. Proof. Consider the bipartite graph GC with parts C and X , where c ∈ C is adjacent to x ∈ X if and only if c(x) = −1. Let d := smax (C). Then since s1 (C) ≤ d and s−1 (C) ≤ d, where 1 and −1 denote the all-ones and all-minus-ones hypotheses3 , neither GC nor its bipartite complement contains an induced matching of size 2 4d d. Atminas [Atm22, Theorem 2.1] showed that there is a function f (d) ≤ (2d2 )(2d ) such that whenever a bipartite graph G = (A ∪ B, E) and its bipartite complement both omit induced matchings of size d, the parts admit partitions A = A1 ∪ · · · ∪ Au and B = B1 ∪ · · · ∪ Bu with u ≤ f (d) such that every induced subgraph G[Ai , Bj ] is 2K2 -free (as induced subgraph). We combine this with the following standard fact about 2K2 -free bipartite graphs. Proposition 1.10 ([MP95]; see [HK07, Theorem 6.3]). If a bipartite graph G = (A ∪ B, E) contains no induced matching with two edges, then there is an ordering B = {b1 , . . . , bm } such that abi ∈ E implies abj ∈ E for all j ≥ i. The adjacency pattern of Proposition 1.10 is realized by points and thresholds on a line, so each block G[Ai , Bj ] in Atminas’s partition, viewed as a sign matrix, has sign-rank at most 2. The matrix A is partitioned into a u × u grid of such blocks with u ≤ f (d), and since sign-rank is subadditive under both horizontal and vertical concatenation, we conclude signrk(A) ≤ 2u2 ≤ 2f (d)2 . 1.1.5

Separation of coindex and list replicability for partial classes.

All three parameters, IndZ2 , coIndZ2 , and lr, extend naturally to partial concept classes C ⊆ {±1, ⋆}X . A distribution µ over X × {±1} is realizable by such a c if it is supported on pairs (x, c(x)) with c(x) ̸= ⋆. One advantage of allowing partial concept classes is that they are flexible enough to encode known classic topological examples. In particular, building on an observation of Frick et al. [FHV26], standard free Z2 -spaces with bounded Z2 -coindex but unbounded Z2 -index can be realized by partial concept classes. Combining this with Theorem 1.1, we obtain a dimension-free separation between coIndZ2 and lr. Corollary 1.11. There exist partial concept classes C ⊆ {±1, ⋆}n with coIndZ2 (C) = O(1)

and

lr(C) = ω(1).

We outline the argument below, leaving the details for Section 6. The argument builds on an observation of Frick, Hosseini, and Vasileuski that every finite free Z2 -simplicial complex arises as ∆C ± for some partial concept class C [FHV26]. Moreover, by Illman’s equivariant triangulation theorem [Ill78], every compact smooth free Z2 -manifold admits a finite Z2 -equivariant triangulation. This gives a recipe for importing standard examples from equivariant topology to partial concept classes. Applying this reduction to the spaces RP2N −1 , with the free Z2 -action induced by multiplication by i on CN , one obtains partial concept classes with bounded coIndZ2 and unbounded IndZ2 [FHV26]. Combined with Theorem 1.1, this gives a dimension-free separation between coIndZ2 and lr. 1.1.6

List replicability under joins and concatenations.

We next record quantitative composition properties of list replicability. Given C1 ⊆ {±1}X1 and C2 ⊆ {±1}X2 over disjoint finite domains X1 and X2 , define their join C1 ∗ C2 ⊆ {±1}X1 ⊔X2 as C1 ∗ C2 := c ∈ {±1}X1 ⊔X2 : c|X1 ∈ C1 and c|X2 ∈ C2 . 3 Conversely, since every h ∈ {±1}X

satisfies sh (C) ≤ s1 (C) + s−1 (C), we have smax (C) ≤ s1 (C) + s−1 (C).

The terminology is motivated by the fact that ∆(C1 ∗C2 )± is homeomorphic to the topological join ∆C ± ∗ ∆C ± : 1 2 since X1 and X2 are disjoint, every realizable distribution for C1 ∗C2 is a convex combination of a distribution supported on X1 and one supported on X2 [CMW25, Lemma 23]. Note that the Z2 -index is subadditive, and the coindex is superadditive under joins (see, e.g., [Mat03]), IndZ2 (C1 ∗ C2 ) ≤ IndZ2 (C1 ) + IndZ2 (C2 ) + 1,

(7)

coIndZ2 (C1 ∗ C2 ) ≥ coIndZ2 (C1 ) + coIndZ2 (C2 ) + 1.

(8)

and In light of Theorem 1.1, it is natural to ask how list replicability behaves under joins. It is not difficult to prove lr(C1 ∗ C2 ) ≤ (lr(C1 ) + 1) · (lr(C2 ) + 1) by essentially running the list-replicable algorithms for C1 and C2 separately on the corresponding parts of the sample and combining their outputs into a single hypothesis on X1 ⊔ X2 : the resulting list consists of all pairs of hypotheses from the two lists. We improve this multiplicative bound to an additive one, which is sharp. Theorem 1.12. Given two concept classes C1 and C2 over disjoint finite domains, we have lr(C1 ∗ C2 ) ≤ lr(C1 ) + lr(C2 ). The proof uses a quantile-style coupling to synchronize the choices of the two LR learners. Instead of taking all pairs of possible outputs, it aligns the two output distributions on a common interval, so only linearly many pairs can appear. The full proof can be found in Section 7. For matrices, Theorem 1.12 gives useful decomposition rules. Given two concept classes C1 and C2 over the same domain X, it follows from the definition that lr(C1 ∪ C2 ) ≤ lr(C1 ) + lr(C2 ), since one can run list-replicable learners for both classes and take the union of the resulting lists (see also Lemma 7.1). This operation corresponds to the vertical concatenation of the associated sign matrices. On the other hand, horizontal concatenation is controlled by joins: if A1 and A2 have the same number of rows, then the concept class associated with [A1 A2 ] is naturally a subclass of the join of the two corresponding concept classes. We thus obtain subadditivity of list replicability under both horizontal and vertical concatenation of matrices. Corollary 1.13. For sign matrices with matching dimensions, lr A1

1.2

≤ lr(A1 ) + lr(A2 )

and

A3 ≤ lr(A3 ) + lr(A4 ). A4

Related work

Sign-rank. The sign-rank of a matrix was introduced by Paturi and Simon [PS86], who observed that vc(A) ≤ signrk(A) as a consequence of the VC dimension of half-spaces. Sign-rank has since become a fundamental quantity in theoretical computer science, with connections to learning theory, communication complexity, circuit complexity, combinatorics, discrete geometry, and Banach space theory; see [HHP+ 22]. Shortly after its introduction, Alon, Frankl, and Rödl [AFR85] used bounds on the number of connected components of real algebraic varieties [Mil64, Tho65, War68] to prove linear lower bounds on the sign-rank of random matrices. For explicit matrices, the VC dimension bound remained the state of the art for nearly two decades, until √ the breakthrough of Forster [For02], who proved the n × n Hadamard matrix Hn satisfies signrk(Hn ) ≥ n, the first super-logarithmic lower bound on the sign-rank of an explicit matrix. Topological methods. The use of topological obstructions in combinatorics has a rich history, with Lovász’s proof of Kneser’s conjecture [Lov78] as a landmark example; see [Mat03] for a comprehensive treatment. The common theme is to associate a Z2 -space to a combinatorial object and extract consequences from equivariant invariants such as the Z2 -index and coindex [MZ02, CLSW04, ST06, STV09]. The sign-rank lower bound of Frick, Hosseini, and Vasileuski [FHV26] via the Z2 -index fits squarely within this framework. 8

List replicability. Replicability, the requirement that an algorithm produce consistent outcomes when repeated under similar conditions, has become a vibrant research area in learning theory, with various rigorous formulations introduced and studied [BLM20, MM22, CMY23, BGH+ 23, KVYZ23, EKK+ 23, EKM+ 23, MSS23, EHKS23, KKL+ 24, KKMV23]. A key notion in this area is global stability, which emerged from the study of differentially private and online learning [BLM20, ABL+ 22]. Chase, Moran, and Yehudayoff [CMY23] later reformulated global stability in the equivalent language of list replicability. Subsequent work has revealed that this notion is intrinsically linked to the geometry and topology of the space of realizable distributions [CMY23, CCMY24, BGHH25, CMW25, BHH+ 26a, BHH+ 26b, BHH+ 26c]. Extremal and intersection-closed concept classes. The study of extremal and intersection-closed classes is motivated by the fact that their combinatorial structure gives rise to natural learning algorithms, sharp PAC sample-complexity bounds, and simple sample-compression constructions [MW16, CCMW22, CCH+ 24, BHH+ 26b, HSW90, HLW94, FW95, BDE98, Kuh99, DJ03, AO07, Dar15, Han16, BHQS21, RR22, Han24]. Relationships between parameters. Frick, Hosseini, and Vasileuski [FHV26] introduced the Z2 -index and the closely related parameter coIndZ2 (C), and showed vc(C) − 1 ≤ coIndZ2 (C) ≤ IndZ2 (C) ≤ signrk(C) − 1. Chase, Moran, and Yehudayoff [CMY23, Theorem 3] proved that vc(C) ≤ lr(C) for every concept class C. The inequality lr(C) ≤ signrk(C) was conjectured in [CMY23], verified there for signrk(C) = 2, and later resolved in full by Blondal et al. [BHH+ 26a]. Finally, the Littlestone dimension is a refinement of the VC dimension that characterizes the optimal mistake bound in online learning; in particular, the VC dimension is a lower bound on the Littlestone dimension. A celebrated result of Bun, Livni, and Moran [BLM20, ABL+ 22] shows that every class with Littlestone dimension d satisfies O(d) lr(C) ≤ 22 .

1.3

Concluding remarks and open problems

How large can the Z2 -index be? The lower bound vc(C) − 1 ≤ IndZ2 (C) provides N × N sign matrices with IndZ2 (A) ≥ log N , namely those with vc(A) = log N . Since a typical N × N sign matrix has sign-rank Ω(N ), (3) leaves a wide gap between this logarithmic lower bound and the polynomial behaviour of sign-rank. It is natural to ask whether the Z2 -index or the list replicability number of an N × N sign matrix can be super-logarithmic, or even polynomial, in N . Evidence so far has pointed in the negative direction: Frick et al. [FHV26] showed that a random N × N sign matrix satisfies IndZ2 (A) = O(log N ) with high probability, and that the N × N Hadamard matrix, the standard example of an explicit matrix with large sign-rank, also satisfies IndZ2 (HN ) = O(log N ). Nevertheless, the logarithmic barrier can be surpassed. Proposition 1.14. There exist N × N sign matrices A with 2 lr(A) − 1 ≥ IndZ2 (A) ≥ coIndZ2 (A) ≥ Ω

log2 N log log N

Proof of Proposition 1.14, originally from [CMW25]. Consider the m × 2m matrix Um , containing a column for every sign pattern on the m rows. Chornomaz, Moran, and Waknine show that it has Z2 -coindex of at least m − 2. Since the coindex is superadditive with respect to joins (recall Section 1.1.6), we take the join of k = m/ log2 m copies of Um . k Um = Um ∗ · · · ∗ Um ,

k k and obtain coIndZ2 (Um ) ≥ (m−2)(m)/ log m. Note Um has mm/ log m = 2m rows and (m/ log m)2m columns. Therefore, it is contained in an N × N sign matrix A, where N = (m/ log m)2m , with log2 N m2 =Ω . 2 lr(A) − 1 ≥ IndZ2 (A) ≥ coIndZ2 (A) ≥ Ω log m log log N

The lower bound provided in Proposition 1.14 is currently the strongest known lower bound on the list replicability and the Z2 -index of any N × N matrix. We conjecture that this bound is essentially tight (see also [FHV26, Question 37]). Conjecture 1.15. Every N × M sign matrix A satisfies lr(A) = O(log N log M ). Upper bounds by a function of VC dimension? Perhaps the most intriguing open question in the study of list replicability is whether lr(C) can be upper bounded by a function of VC dimension. Originally posed in [CMY23], this question was resolved for extremal concept classes in [BHH+ 26b], where it was shown that lr(C) = Θ(vc(C)). However, the question remains open for arbitrary finite concept classes. Moreover, our result that IndZ2 (C) = O(lr(C)) suggests a natural addition to the question: Problem 1.16. Can IndZ2 (C) or lr(C) be bounded by a function of vc(C)? Note that a positive answer to Problem 1.16 would also imply coIndZ2 (C) is bounded by a function of vc(C). This question has already been asked [CMW25] as it has important implications for the learnability of large-margin half-spaces. Embeddings. One potential approach to resolving Problem 1.16 is to embed the concept class C into an extremal or intersection-closed concept class while keeping the VC dimension small. Recall that, in both settings, IndZ2 and lr are bounded above linearly by vc. The problem of embedding into extremal concept classes has been widely studied and remains open [MW16, CCH+ 24]. The analogous problem for intersection-closed classes was studied by Hanneke in [Han24] through the minimum star number smin . Hanneke showed that if vc(C) = 1, then smin (C) = 1; equivalently, every concept class of VC dimension 1 can be embedded into a generalized intersection-closed class of VC dimension 1. On the other hand, Hanneke also observed that there exists a family of finite concept classes with VC dimension 3 and arbitrarily large minimum star number smin . This implies that, in general, one cannot embed an arbitrary concept class into an intersection-closed class without incurring a blow-up in VC dimension. Hanneke asked what happens in the case vc(C) = 2. We show that smin can be arbitrarily large in this case as well. Theorem 1.17. For every k ≥ 2, there is a finite total concept class Ck with vc(Ck ) = 2

and

smin (Ck ) ≥ k.

Proof. Let Xk = [k] × [k], and write Ri = {i} × [k] for the ith row. For convenience, we will treat concepts as subsets of X , that is c(x) = 1 if x ∈ c and c(x) = −1 otherwise. Define Ck = {∅} ∪ {Ri : i ∈ [k]} ∪ {Ri \ {x} : i ∈ [k], x ∈ Ri }. First, vc(Ck ) ≥ 2. Indeed, if x, y ∈ Ri are distinct, then ∅, Ri , Ri \{x}, Ri \{y} realize all four labelings on {x, y}. Also, since any concept can only have 1’s on one row Ri , it is not hard to see vc(Ck ) ≤ 2. We conclude vc(Ck ) = 2. Now fix any center function h : Xk → {−1, 1}. We show that sh (Ck ) ≥ k. If every row Ri contains some point xi with h(xi ) = −1, let S = {x1 , . . . , xk }. 10

Then ∅ agrees with h on S, and for each i ∈ [k], the concept Ri flips exactly the point xi on S. Hence S is a star of size k centered at h. Otherwise, some row Ri is entirely labeled 1 by h. Take S = Ri . Then the concept Ri agrees with h on S, and for each x ∈ Ri , the concept Ri \ {x} flips exactly x on S. Hence S is again a star of size k centered at h. Thus sh (Ck ) ≥ k for every h, so smin (Ck ) ≥ k.

1.4

Technical overview of Theorem 1.1 and Theorem 1.2

In this section, we briefly describe how we prove Theorem 1.1 and Theorem 1.2. Complete proofs are in Section 3. Bounding index by LR.

Theorem 1.1 states that for any concept class C, IndZ2 (C) ≤ 2 lr(C) − 1.

To prove this, we first use the fact that a list-replicable algorithm with list size L gives an antipodalfree open cover of the distribution space ∆C ± , where each point is contained in at most 2L open sets (see Theorem 2.11). This bounded overlap allows us to use a partition of unity to construct a continuous map from ∆C into R2L \ {0}. The antipodal symmetry of the cover ensures that this map is Z2 -equivariant, while antipodal-freeness ensures that the image avoids the origin. After normalizing, we obtain a Z2 -equivariant map Z

2 ∆C −→ S2L−1 .

Therefore, by the definition of the Z2 -index, IndZ2 (∆C ) ≤ 2L − 1. Separating index from sign-rank. The separation of sign-rank and index in Theorem 1.2 hinges on a particular family of matrices Bq for which signrk(Bq ) grows polynomially in q, while IndZ2 (Bq ) is bounded. This family was first used by Alon, Moran, and Yehudayoff to separate sign-rank and VC dimension [AMY16]. Definition 1.18 (Finite Projective Plane). Let PG(2, q) be the finite projective plane of order q. It is an incidence geometry (P, L) with N = q 2 + q + 1 points and lines such that: 1. Any two distinct lines ℓ1 , ℓ2 ∈ L intersect in exactly one point p ∈ P. 2. Any two distinct points p1 , p2 ∈ P are contained in exactly one line ℓ ∈ L. Let Bq be the N × N indicator matrix of this incidence geometry. That is, Bq has rows indexed by lines and columns indexed by points, and ( 1 if pj ∈ ℓi (Bq )ij = −1 if pj ∈ / ℓi . Matrices of this form were useful for the separation of VC dimension and sign-rank because of the polynomial growth of signrk(Bq ), a result which we will apply directly for our separation of index and sign-rank. Theorem 1.19 ([AMY16]). The N × N indicator matrix Bq of PG(2, q) satisfies the inequality 1 q2 − 1 signrk(Bq ) ≥ √ ≥ N 4. q(q − 1)

The remaining half of our separation requires bounding IndZ2 (∆Bq ) by a constant. This is done by combining Theorem 1.1 with a list-replicable algorithm for Bq , which we give in Theorem 3.2. 11

The algorithm. Here we treat the matrix Bq as a concept class with concepts labeled by lines and domain points labeled by points. We design a simple list-replicable algorithm for Bq that shows lr(Bq ) ≤ 3. The algorithm proceeds as follows. If the sample contains two distinct points labeled 1, then there is a unique line passing through both of them, so the algorithm outputs that line. Otherwise, if the sample contains only a single point labeled 1 and that point has low sampling probability, the algorithm ignores it, since doing so affects the error only negligibly with high probability. Finally, if the sample contains exactly one point labeled 1 and that point has high sampling probability, the algorithm outputs the indicator function of that point. The complete proof of this step can be found in Theorem 3.2. √ Combining the two steps, we have that the family Bq has IndZ2 (Bq ) ≤ 5, but signrk(Bq ) = Ω( q) = Ω(N 1/4 ).

Preliminaries

In this section, we collect all topological and learning-theoretic tools that we use. We first introduce basic notions from Z2 -equivariant topology, which allows us to formally define the Z2 -index of a sign matrix and its corresponding concept class. Afterwards, we go through some fundamental learning theoretical definitions and results, including list replicability and its topological and algorithmic interpretations.

2.1

The Z2 -topological framework

Definition 2.1 (Simplicial Complex). An abstract simplicial complex K on a vertex set V is a collection of finite subsets of V that are closed under taking subsets. Its elements are called simplices and its dimension is maxσ∈K |σ| − 1. The geometric realization of K is the topological space ( ) X X V ∥K∥ := x ∈ R : x = λv ev , λv ≥ 0, λv = 1, supp(x) ∈ K , v∈V

v∈V

where ev denotes the standard basis vector indexed by v and supp(x) = {v : λv > 0}. Definition 2.2 (Free Z2 -Simplicial Complex). A free Z2 -simplicial complex is a pair (K, ν) where K is an abstract simplicial complex and ν is a fixed-point-free simplicial involution, i.e., a simplicial map ν : K → K satisfying ν ◦ ν = idK and ν(σ) ̸= σ for every σ ∈ K. Definition 2.3 (Free Z2 -Space). A free Z2 -space is a pair (X, ν) where X is a topological space and ν is a continuous fixed-point-free involution, i.e., a continuous map ν : X → X satisfying ν ◦ ν = idX and ν(x) ̸= x for every x ∈ X. The geometric realization of a free Z2 -simplicial complex is naturally a free Z2 -space. Indeed, if K is a free Z2 -simplicial complex with involution ν, the map X X λv ev 7→ λv eν(v) v∈V

v∈V

is an involution on ∥K∥. Example 2.4. The n-dimensional sphere Sn = {x ∈ Rn+1 : ||x|| = 1} equipped with the canonical involution ν(x) = −x is a free Z2 -space. Definition 2.5 (Antipodal Map). Let (X, ν) and (Y, ω) be free Z2 -spaces. We say a map f : X → Y is Z

2 antipodal if it commutes with the involutions on each space, that is f ◦ ν = ω ◦ f . We write f : X −→ Y to denote that f is an antipodal map between X and Y .

The antipodal terminology comes from the fact that f cannot have f (x) = f (ν(x)) for any x ∈ X due to the involutions ν and ω being fixed-point-free. Definition 2.6 (Z2 -index). The Z2 -index of a free Z2 -space (X, ν) is the minimum integer n such that there is an antipodal map from X into the n-dimensional sphere. Z

2 Sn }. IndZ2 (X) := min{n ∈ N : ∃f : X −→

It is also natural to instead consider the smallest sphere that maps antipodally into X, giving us the notion of Z2 -coindex. Definition 2.7 (Z2 -coindex). The Z2 -coindex of a Z2 space X is the maximum n such that there is an antipodal map from Sn into X. Z

2 X}. coIndZ2 (X) := max{n ∈ N : ∃f : Sn −→

The following is a generalization of the classical Borsuk–Ulam Theorem. Theorem 2.8 (Borsuk–Ulam). Let (X, ν) be a free Z2 -space. Then coIndZ2 (X) ≤ IndZ2 (X). We refer the reader to Jiřı́ Matoušek’s excellent textbook on topological methods in combinatorics for more details on Z2 -spaces and their applications to combinatorics [Mat03, Section 5].

2.2

The Z2 -index of sign matrices and concept classes

To prove our results in full generality, we will work in the broader framework of partial sign matrices and partial concept classes. If A ∈ {1, −1, ⋆}M ×N is a partial sign matrix, the sign-rank of A, denoted signrk(A), is the minimum rank of a real matrix B that captures the sign patterns of A. That is sign(Bij ) = Aij

for every i ∈ [M ], j ∈ [N ] with Aij ̸= ⋆.

Partial concept classes. Partial sign matrices can also be interpreted as partial concept classes. Given a domain X , a partial concept class C ⊆ {+1, −1, ⋆}X is a family of functions, called concepts, mapping X → {+1, −1, ⋆}. These are fundamental objects in learning theory because they encode bias, which is a prerequisite for any meaningful definition of learning. The partial concept class of a partial sign matrix A ∈ {1, −1, ⋆}M ×N is a family CA ⊆ {+1, −1, ⋆}[N ] with (partial) concepts given by rows of A. That is, ci : j 7→ Aij . Space of realizable distributions. We say that a distribution µ ∼ X × {±1} is realizable by a partial concept class C if there exists a partial concept c such that c(x) = b for each (x, b) in the support of µ. We denote the set of all realizable distributions µ by ∆C := {µ : µ realizable by C}. When equipped with the total variation (TV) distance, ∆C forms a metric space. ∆C has a natural geometric realization as a subset of the ℓ1 -sphere. ∆C := µ ∈ RX : ||µ||1 = 1 and ∃c ∈ C with c(x) = bµ(x) ∀(x, b) ∈ supp(µ) ⊆ RX . Note that each partial concept c ∈ C corresponds to a simplex σc ∈ ∆C : σc = conv({b × ex : x ∈ X , c(x) = b}) 13

(9)

where {ex }x∈X is the standard basis of RX .

∆C ⊂ R3

∆C +-+ ++-

+++

--+ -++

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 free Z2 -space with a natural Z2 -action given by negating labels: µ 7→ −µ, where −µ assigns mass µ(x, b) to (x, −b). Definition 2.9 (Index/Coindex). Let A be a partial sign matrix and let CA be its associated partial concept class. Then we define IndZ2 (A) := IndZ2 (CA ) := IndZ2 (∆C ± ) A

coIndZ2 (A) := coIndZ2 (CA ) := coIndZ2 (∆C ± ) A

2.3

List replicability

The motivation for our discussion of the concept class of a sign matrix in the previous section is that this object allows us to leverage existing list replicability techniques from learning theory. S ∞ A learning rule is a (possibly randomized) function A that maps any sample S ∈ n=0 (X × {±1})n to X a hypothesis A(S) ∈ {±1} . The error or population loss of a hypothesis with respect to a distribution µ over X × {±1} is measured as lossµ (h) = P(x,y)∼µ [h(x) ̸= y]. Definition 2.10 (List Replicability, [CMY23, DPVWV23]). A learning rule A is an (ϵ, L)-list-replicable learner for a partial concept class C if for every δ > 0 there exists a sample complexity n := n(δ) such that the X following holds. For every distribution µ realizable by C, there exists a list of hypothesis h1 , . . . , hL ∈ {±1} such that lossµ (hi ) ≤ ϵ ∀i and PS∼µn [A(S) ∈ {h1 , . . . , hL }] ≥ 1 − δ. The ϵ-list replicability number of C is lr(C, ϵ) := min{L : ∃(ϵ, L)-list-replicable learner for C}, with lr(C, ϵ) = ∞ if none exists. The list replicability number of C is lr(C) := sup lr(C, ϵ). ϵ>0

We say C is list-replicable if lr(C) < ∞. 14

One of the advantages of list replicability is that this purely learning theoretic definition also admits a topological description via closed covers of ∆C . Recall that for each h ∈ {±}X we defined σh = conv({b × ex : x ∈ X , h(x) = b}) where {ex }x∈X is the standard basis of RX . Now for each hypothesis h ∈ {±1}X let Bϵ (σh ) denote set of all points in ∆{±1}X (equivalently the cross-polytope boundary) that are within total variation distance less than ϵ from the simplex σh . Denote by Bϵ (σh ) the respective closure. We call the sets Bϵ (σh ) and Bϵ (σh ) the open and closed ϵ-loss sets of h because they contain all distributions µ ∈ ∆C for which lossµ (h) < ϵ and lossµ (h) ≤ ϵ respectively. A recent line of work in [CMY23, CCMY24, BHH+ 26b] has shown a correspondence between listreplicable learners for C and closed/open covers of ∆C . In both cases, list size corresponds to the overlap degree of the cover, which we define as the maximum number of sets in the cover with a common non-empty intersection. Theorem 2.11 ([CCMY24, Corollary 23], [BHH+ 26b, Theorem A]). Let C ⊆ {±1, ⋆}X be a finite partial concept class and let ϵ > 0. • (Closed cover characterization) The ϵ-list replicability number lr(C, ϵ) equals the minimum integer L for which there exists a closed cover F = {Fh : h ∈ {±1}X } of ∆C with overlap degree at most L and Fh ⊆ B ε (σh ) for every h ∈ {±1}X . • (Open cover characterization) If L := lr(C, ϵ), then for every η > ϵ there exists an open cover U = {Uh : h ∈ {±1}X } of ∆C with overlap degree at most L such that Uh ⊆ Bη (σh ) for every h ∈ {±1}X . Conversely, if for some η > 0 and L ∈ N there exists an open cover U = {Uh : h ∈ {±1}X } of ∆C with overlap degree at most L such that Uh ⊆ Bη (σh ) for every h ∈ {±1}X , then there exists some ϵ < η such that lr(C, ϵ) ≤ L. The closed cover characterization of list replicability was shown in [CMY23] for total concept classes, but the argument immediately generalizes to partial concept classes. The open cover characterization is closely related, and was studied in a stronger form as simplicial covering dimension in [BHH+ 26b].

Separating sign-rank and index

Recall from Section 1.4 that our separation of sign-rank and index in Theorem 1.2 leverages the family of incidence matrices Bq for the finite projective planes PG(2, q). We are guaranteed the polynomial growth of signrk(Bq ) from Theorem 1.19, so this section will collect the proofs of Theorem 1.1 and Theorem 1.2 to bound IndZ2 (Bq ) by a constant.

3.1

List replicability number upper bounds index

In this section, we prove our main technical result Theorem 1.1, stated here in a slightly stronger form. Theorem 3.1. For every (partial) concept class C and error parameter ε ∈ (0, 12 ), IndZ2 (C) ≤ 2 lr(C, ε) − 1. The argument begins by producing a closed cover of ∆C with small overlap degree, as guaranteed by Theorem 2.11. We use basic topology to extend that cover to an open cover of ∆C ± which respects the Z2 structure of that space. This step is necessary because IndZ2 (C) is by definition a property of ∆C ± rather than ∆C . From here, we map ∆C ± into low-dimensional Euclidean space, which we in turn project into a sphere. Z

2 2 ∆C ± −→ R2L \ 0 −→ S2L−1 .

By definition, the composition of these maps witnesses an upper bound on IndZ2 (C). The construction of Z

2 R2L was discovered by considering the nerve complex associated with the open cover of the map ∆C ± −→ ∆C ± . This is a simplicial complex that encodes intersection data, making it a natural candidate to analyze overlap degree.

Proof of Theorem 3.1. For convenience, set L := lr(C, ε). Let A be an (ε, L)-list-replicable learner for C. By the closed cover characterization of list replicability in T heorem 2.11, A induces a closed cover of ∆C given by F = {Fh : h ∈ {±1}X }, where the overlap degree of F is L

and

Fh ⊆ Bε (σh ) for all h ∈ {±1}X .

Recall that IndZ2 (C) is defined to be the Z2 -index of ∆C ± . Since ∆C is closed subspace of ∆C ± , each set Fh remains closed under the natural inclusion ∆C ,→ ∆C ± . Hence, the family F ′ := {Fh′ : Fh′ = Fh ∪ (−F−h ) for some h ∈ {±1}X }. ′ is a closed cover of ∆C ± with overlap degree at most 2L satisfying Fh′ ⊆ Bϵ (σh ) and Fh′ = −F−h for all h. Now pick any ϵ0 ∈ (ϵ, 1/2). Because ∆C ± is compact, we can extend each closed set Fh′ to an open set Uh ⊆ Bϵ0 (σh ) without increasing the overlap degree of the family and while preserving the antipodal symmetry Uh = −U−h 4 . Then U := {Uh : h ∈ {±1}X } is a finite open cover of ∆C ± with overlap degree at most 2L such that Uh ⊆ Bϵ0 (σh ) and Uh = U−h for all h. Since ∆C ± is a compact metric space, there exists a partition of unity {ϕh }h subordinate to the open cover U [Rud87, Theorem 2.13]. That is, there exists a collection of maps ϕh : ∆C ± → [0, 1] such that X supp ϕh ⊆ Uh and ϕh ≡ 1. h

We can make an antipodally symmetric version of {ϕh }h by setting ϕ∗h (x) :=

1 (ϕh (x) + ϕ−h (−x)). 2

Note that the antipodal symmetry Uh = −U−h guarantees that supp ϕ∗ (x) ⊆ Uh . Next, let {ph }h ⊆ R2L be a set of points in general position such that p−h = −ph . That is, a subset P ⊂ {ph } of size 2L contains zero in its convex span if and only if P contains a pair {ph , p−h } for some h. Using the antipodally symmetric partition of unity ϕ∗ and the points {ph }h , we define an antipodal map Z

2 f : ∆C ± −→ R2L by

f (x) =

ϕ∗h (x)ph .

We claim that 0 ∈ / im(f ). Indeed, for every x ∈ ∆C ± , the overlap degree of U ensures ϕ∗h (x) is nonzero for at most 2L hypotheses h. Additionally, ε0 < 1/2 implies that no Uh contains both x and −x, so ϕ∗ must be zero for at least one of the two points. Thus, the coefficients of ph and p−h cannot both be positive. It follows that f (x) is a convex combination of at most 2L points of P , which does not contain both ph and p−h . Since P is in general position, 0 ∈ / im(f ). We may therefore project the image of f into the sphere S2L−1 ⊂ R2L to get a map f Z2 : ∆C ± −→ S2L−1 . ||f ||2 Exhibiting such an antipodal map into the sphere shows that IndZ2 (∆C ± ) ≤ 2L−1 by definition of index. 4 Let d : ∆ C ± → [0, 1] be a function measuring the total variation distance d(x) from a point x ∈ ∆C to the L + 1’st closest set Fh′ . By compactness, this function achieves a strictly positive minimum β. Take Uh := ∪x∈F ′ Bβ/2 (x). h

3.2

A list-replicable algorithm for PG(2, q)

As defined in Definition 1.18, recall the incidence geometry PG(2, q) = (P, L). Let Cq denote the corresponding concept class Cq := {cℓ : ℓ ∈ L} cℓ : P → {±1} ( 1 if p ∈ ℓ p 7→ −1 otherwise. We exhibit a list-replicable algorithm for Cq . By sampling random points x ∈ P and whether they lie on a line ℓ, the learner’s goal is to output a predictor of whether future points lie on the same line. Theorem 3.2. The list replicability number of Cq satisfies lr(Cq ) ≤ 3. Proof. We extend the concept class Cq to a larger hypothesis class Hq Hq = {cℓ : ℓ ∈ L} ∪ {cp : p ∈ P} ∪ {c−1 }, where c−1 is the all-minus hypothesis, and cp is the indicator function for a single point p, evaluating to 1 on p and −1 everywhere else. Since Hq is finite, we have by the union bound and Hoeffding’s inequality5 that there exists an n(ϵ, δ) such that for any D ∈ ∆Cq , we can estimate the population loss of all hypotheses in Hq simultaneously: " # ϵ PS∼Dn sup | lossS (h) − lossD (h)| ≤ ≥ 1 − δ. (10) 8 h∈Hq Next, we define the learning rule A. For any ϵ, δ, let its sample size be n(ϵ, δ) so as to satisfy (10). Algorithm 1 The learning rule A 1: Sample S = (S1 , . . . , Sn ) ∼ D n . 2: for p ∈ P do 3: Let D̂(p) = n1 |{i ∈ [n] : Si = (p, 1)}|. 4: end for 5: Let P0 ← {p ∈ P : D̂(p) > 0} 6: Let P1 ← {p ∈ P : D̂(p) > 7ϵ/8} 7: if |P0 | ≥ 2 then 8: Output cℓ , where ℓ is the unique line containing all points in P0 . 9: else if |P1 | = 1 then 10: Output cp , where P1 = {p}. 11: else 12: Output c−1 . 13: end if We start by confirming that this algorithm is a PAC learner. By (10), with probability ≥ 1 − δ, sup | lossS (h) − lossD (h)| ≤ h∈Hq

ϵ . 8

5 Let c ∈ R and let x , . . . , x be independent random variables with x ∈ [−c, c] and E[x ] = 0. For any t > 0, n 1 i i

" P

n X

xi ≥ t ≤ 2e− 2c .

i=1

Denote this event by E. Case 1. Whenever |P0 | ≥ 2, the hypothesis output is correct and has no loss. Case 2. If P0 = P1 = {p}, then A(S) = cp and lossS (cp ) = 0. Hence, given E, we have lossD (cp ) ≤

ϵ . 8

Case 3. If |P0 | = 0, then once again, the hypothesis output has no empirical loss, so given E, lossD (c−1 ) ≤

ϵ . 8

Case 4. Finally, if P0 = {p} but P1 = ∅, then given E, we have lossD (c−1 ) ≤ lossS (c−1 ) +

ϵ 7ϵ ϵ ≤ + = ϵ. 8 8 8

Next, we show the list replicability of A. Claim 3.3. Given E, the algorithm A cannot output cp and cp′ for two distinct points p ̸= p′ . Proof. Suppose that A outputs cp on some sample satisfying E. Then P0 = P1 = {p}, so lossS (c−1 ) = D̂(p) > 7ϵ/8 and lossS (cp ) = 0. By E, lossD (c−1 ) >

ϵ 3ϵ 7ϵ − = , 8 8 4

lossD (cp ) ≤

ϵ . 8

Moreover, since cp is output, the point p appears with label 1, so p lies on any line realizing D. Hence D(p) = P(x,y)∼D [x = p] = | lossD (c−1 ) − lossD (cp )| >

5ϵ . 8

Now let S ′ be any sample satisfying E. Again using E for the two hypotheses c−1 and cp , D̂S ′ (p) = | lossS ′ (c−1 ) − lossS ′ (cp )| ≥ | lossD (c−1 ) − lossD (cp )| −

2ϵ 3ϵ > . 8 8

Thus, every sample satisfying E contains at least one copy of (p, 1). Therefore, if both cp and cp′ could be output on samples satisfying E, then every sample satisfying E would contain both (p, 1) and (p′ , 1). But then |P0 | ≥ 2, and the algorithm would output the unique line through p and p′ , not a point hypothesis. This contradiction proves the claim. By Claim 3.3, we see that when E holds, A has population loss less than ϵ, and outputs one of at most 3 different hypotheses. Therefore, lr(Hq ) ≤ 3.

A height-based list replicability algorithm

In [FHV26], Frick et al. used a combinatorial notion of the height of a simplicial complex to upper bound the index of a concept class. We show that this height is an upper bound for list replicability as well. Recall from Section 1.1.3 the definition of the junction closure J (C) of a partial concept class C ⊆ {±1, ⋆}X : ( ) \ J (C) = c : ∅ ̸= S ⊆ C c∈S

Then, the height H(C) measures the length of the longest inclusion chain in J (C). We restate Theorem 1.3 for completeness. 18

Theorem 1.3 (Height controls list replicability). For every finite partial concept class C ⊆ {±1, ⋆}X , lr(C) ≤ H(C). Frick et al. applied their result to show that with high probability, random sign matrices have index O(log n). Theorem 4.1 (Random sign matrices have O(log n) height and index, [FHV26]). Let A ∈ {±1}N ×N be a sign matrix with entries sampled independently and uniformly at random. Then, there exists some constant C > 0 such that with probability 1 − o(1), H(A) ≤ C · log N, and therefore IndZ2 ≤ 2C · log N. Corollary 4.2 (Random sign matrices have O(log n) list replicability). For A ∈ {±1}N ×N with entries sampled independently and uniformly at random, with probability 1 − o(1), lr(A) ≤ C · log N as well. Proof. The corollary follows directly from Theorems 1.3 and 4.1. To prove Theorem 1.3, we give an algorithm that, with high probability, will only ever output c contained within a single chain of J (C). Therefore, the list replicability of this algorithm will be naturally bounded by the height of C. The algorithm is fairly similar to that described in Theorem 3.2. We estimate the error of every partial hypothesis in J (C), and pick the smallest one that has “low error”. In particular, our threshold for “low error” diminishes as the size of the hypothesis grows, so that we can guarantee that if any two partial hypotheses have low enough error, so does their junction. This way, we prevent any anti-chains in our output set. Proof of Theorem 1.3. Let the domain X of C have size |X | = N . Since J (C) is finite, by Hoeffding’s inequality, for every ϵ, δ > 0, there exists an n(ϵ, δ) such that for any D ∈ ∆C , we can estimate the population loss of all hypotheses in J (C) simultaneously: " # ϵ PS∼Dn sup | lossS (c) − lossD (c)| ≤ N ≥ 1 − δ. (11) 4 c∈J (C) We define the learning rule A. For any ϵ, δ, let its sample size be n(ϵ, δ) so as to satisfy (11). Denote by E the event that all losses are estimated within ϵ4−N . Denote by |c| the number of non-⋆ points in the concept. Algorithm 2 The learning rule A 1: Sample S = (S1 , . . . , Sn ) ∼ D n . 2: for c ∈ J (C), ordered from smallest to largest by size |c| do 3: if lossS (c) ≤ ϵ · 4−|c| then 4: Output c, or any completion of c. 5: end if 6: end for 7: Output ERROR (the algorithm never reaches this state)

First of all, it is clear that A is a PAC learner. If E holds, then ϵ ϵ ϵ lossD (A(S)) ≤ N + lossS (A(S)) ≤ N + |A(S)| ≤ ϵ. 4 4 4 Since A(S) can be a partial hypothesis, outputting any completion of it will never make the error grow. Claim 4.3. Let event E hold. Then, if c1 and c2 both satisfy the output requirement in line 3 of Algorithm 2, so does c1 ∩ c2 . Proof. Without loss of generality, if c1 ⊆ c2 , then this holds trivially. Otherwise, |c1 ∩ c2 | < min{|c1 |, |c2 |}. Note that c1 ∩ c2 is only correct on a sample if both c1 and c2 are. Thus, lossD (c1 ∩ c2 ) = P(x,y)∼D [c1 (x) ̸= y or c2 (x) ̸= y] ≤ P(x,y)∼D [c1 (x) ̸= y] + P(x,y)∼D [c2 (x) ̸= y] ≤ lossD (c1 ) + lossD (c2 ) ≤ lossS (c1 ) + lossS (c2 ) + ≤ ≤ ≤

ϵ 4|c1 |

ϵ 4|c2 |

2ϵ 4N

4ϵ 4min{|c1 |,|c2 |} ϵ 4| c1 ∩ c2 |

It is clear that J (C) is closed under taking junctions, so c1 ∩ c2 ∈ J (C), and would be output first if both c1 and c2 fit the conditions. As a result of this claim, so long as E holds, no two concepts in an antichain will be output. Thus, so long as A doesn’t output ERROR, when E holds, it will only output hypotheses from a single chain, so at most H(C) different hypotheses. Finally, A will never output ERROR, for the distribution D comes from ∆C , and thus some c ∈ C ⊆ J (C) has 0 error on it. So if all else fails, that c always fits the conditions to be output by A. Notice that this algorithm can, instead of outputting partial hypotheses, output any completion desired. In particular, many of the partial hypotheses in J (C) may have common completions. Therefore, by using specific completions, better list replicability bounds may be obtained.

Height and eluder dimension

We now prove a more general form of Proposition 1.4, stated in the introduction, that the height parameter coincides with the eluder dimension up to an additive constant. We keep the notation from Section 1.1.3: J (C) is the junction closure of C, and g ⪯ h means that g is a restriction of h. For a partial concept h, write supp(h) := {x ∈ X : h(x) ̸= ⋆}. Definition 5.1 (Height relative to a base concept). Fix a finite partial concept class C ⊆ {±1, ⋆}X and a base concept c′ ∈ C. Define the height of C relative to c′ by H(C; c′ ) := sup {m : ∃h1 , . . . , hm ∈ J (C) such that h1 ≺ h2 ≺ · · · ≺ hm = c′ } . This rooted version recovers the height from the introduction: H(C) = sup H(C; c′ ). c′ ∈C

Also, recall the definition of the eluder dimension. We extend the definition by [LKFS22] to partial concept classes. 20

Definition 5.2 ([LKFS22]). Fix a finite partial concept class C ⊆ {±1, ⋆}X and a base concept c′ ∈ C. The eluder dimension of C relative to c′ , denoted Edim(C, c′ ), is the largest m such that there exist points x1 , . . . , xm ∈ supp(c′ ) and concepts c1 , . . . , cm ∈ C such that, for every i ∈ [m], ci (xi ) ̸= c′ (xi ), (ci (xi ) = ⋆ allowed) while for every earlier point xj , j < i,

ci (xj ) = c′ (xj ).

Define the eluder dimension of C by Edim(C) := supc′ ∈C Edim(C, c′ ). Proposition 5.3 (Height equals eluder dimension). For every finite partial concept class C ⊆ {±1, ⋆}X and every base concept c′ ∈ C, H(C, c′ ) = Edim(C, c′ ) + 1. In particular, H(C) = Edim(C) + 1. Proof. We prove both inequalities. First suppose Edim(C, c′ ) = m. For i = 0, 1, . . . , m, define \ hi = ({c′ } ∪ {ci+1 , ci+2 , . . . , cm }) , and note that h0 ≺ h1 ≺ · · · ≺ hm = c′ . Therefore there is a strict chain of m + 1 partial concepts, so H(C, c′ ) ≥ m + 1. Conversely, suppose H(C, c′ ) = m. Then there exist h1 ≺ · · · ≺ hm = c′ in J (C). For each i = 1, . . . , m−1, since hi ≺ hi+1 , choose a point xi ∈ X such that hi+1 (xi ) ∈ {±1}. T Because hi+1 ⪯ c′ , we have hi+1 (xi ) = c′ (xi ). Suppose hi = c∈Si c for some Si ⊆ C. There exists some ci ∈ Si such that ci (xi ) ̸= c′ (xi ) and ci (xj ) = c′ (xj ) for all j < i. hi (xi ) = ⋆

and

Thus the domain points x1 , . . . , xm−1 together with the concepts c1 , . . . , cm−1 form an eluder sequence with base concept c′ . Therefore Edim(C, c′ ) ≥ m − 1. Combining the two inequalities, H(C, c′ ) = Edim(C, c′ ) + 1.

Separation of coindex and list replicability

In this section, we discuss Corollary 1.11, which we restate below. Corollary 1.11. There exist partial concept classes C ⊆ {±1, ⋆}n with coIndZ2 (C) = O(1)

and

lr(C) = ω(1).

This result follows from combining our Theorem 1.1 with a strategy of [FHV26]. We have shown that lr(C) is bounded from below by IndZ2 (C), and it is know that the projective planes RP2N −1 are free Z2 spaces separating IndZ2 and coIndZ2 . To obtain that separation for IndZ2 (C) and coIndZ2 (C), we realize each RP2N −1 as the space of realizable distributions ∆C ± for some partial concept class C. The last step arises from an argument of Frick, Hosseini, and Vasileuski, which demonstrated that every finite free Z2 -simplicial complex arises as the sign complex for some partial sign matrix [FHV26]. The sign complex is a simplicial complex associated with a partial sign matrix, and it parallels the role of the space of realizable distributions in our discussion of partial concept classes. The same proof in [FHV26] can be adapted to our setting: Lemma 6.1. Every finite free Z2 -simplicial complex K is isomorphic to ∆C ± for a partial concept class C. Proof. A fixed-point-free involution ν on a finite simplicial complex K pairs vertices of K as (v, ν(v)). Since K is finite, we may index these pairs by j ∈ [N ]. Likewise, the facets of K also come in pairs (F, ν(F )), which we can index by i ∈ [M ]. Now define a partial concept class CK ⊆ {+1, −1, ⋆}N of M concepts given by   +1 if vj ∈ Fi ci (j) = −1 if ν(vj ) ∈ Fi   ⋆ otherwise.

Moreover, nice enough Z2 -free spaces can be given a Z2 -free simplicial structure through triangulation. This is a classical result of Sören Illman. Theorem 6.2 (Illman’s Theorem [Ill78]). Every compact smooth free Z2 -manifold admits a finite Z2 equivariant triangulation. Combining Lemma 6.1 and Theorem 6.2 allows us to import the crucial separating example RP2N −1 . Proof of Corollary 1.11. As stated in [Mat03, page 101] (also see [FHV26]), the projective space RP2N −1 can be equipped with the fixed-point-free involution induced by multiplication by i on CN . Moreover, this gives the separation coIndZ2 (RP2N −1 ) = O(1)

and

IndZ2 (RP2N −1 ) = ω(1).

By Theorem 6.2, there is an antipodal homeomorphism between the free Z2 -space RP2N −1 and a simplicial complex KN . Since IndZ2 and coIndZ2 are defined using topological properties of antipodal maps, it follows that KN is also a separating example: coIndZ2 (KN ) = O(1)

and

IndZ2 (KN ) = ω(1).

Applying Lemma 6.1 yields a family of partial concept classes CN with the property that ∆C ± is isomorphic to KN . Using once more that IndZ2 and coIndZ2 are invariant under isomorphism completes the proof. coIndZ2 (CN ) = O(1)

and

IndZ2 (CN ) = ω(1).

Composition properties for list replicability

In this section, we prove some properties of list replicability under joins and concatenations.

Lemma 7.1 (Concatenation). Let C1 , C2 ⊆ {±1}X be concept classes over the same finite domain X . Then, for every ϵ > 0, lr(C1 ∪ C2 , ϵ) ≤ lr(C1 , ϵ) + lr(C2 , ϵ). Consequently, lr(C1 ∪ C2 ) ≤ lr(C1 ) + lr(C2 ). Proof. Fix ε > 0 and let Li := lr(Ci , ε) for i = 1, 2. By Theorem 2.11, for each i ∈ {1, 2} there is a closed cover Fi = {Fhi : h ∈ {±1}X } of ∆Ci such that the overlap degree of Fi is at most Li , and Fhi ⊆ Bε (σh ) for every h ∈ {±1}X . Since ∆C1 ∪C2 = ∆C1 ∪ ∆C2 , define, for every hypothesis h ∈ {±1}X , the closed set Fh := Fh1 ∪ Fh2 ⊆ ∆C1 ∪C2 . Then F := {Fh : h ∈ {±1}X } is a closed cover of ∆C1 ∪C2 with overlap degree at most L1 + L2 satisfying Fh ⊆ Bε (σh ),. Again applying Theorem 2.11 gives lr(C1 ∪ C2 , ϵ) ≤ L1 + L2 . Taking the supremum over ϵ > 0 yields lr(C1 ∪ C2 ) ≤ lr(C1 ) + lr(C2 ).

Theorem 7.2 (Join of classes). Let C1 ⊆ {±1} 1 and C2 ⊆ {±1} 2 be concept classes over finite disjoint domains. Define X ⊔X C1 ∗ C2 := {c1 ⊔ c2 : c1 ∈ C1 , c2 ∈ C2 } ⊆ {±1} 1 2 . Then for every ε > 0, lr(C1 ∗ C2 , ε) ≤ lr(C1 , ε/4) + lr(C2 , ε/4). Consequently, lr(C1 ∗ C2 ) ≤ lr(C1 ) + lr(C2 ). Proof. Fix ϵ > 0 and let Li := lr(Ci , ε/4) for i = 1, 2. By the open-cover characterization of list replicability in Theorem 2.11, there are open covers n o n o X X U = Uh : h ∈ {±1} 1 and V = Vg : g ∈ {±1} 2 of ∆C1 and ∆C2 , respectively, such that the overlap degree of U is at most L1 , the overlap degree of V is at most L2 , and Uh ⊆ Bε/3 (σh ), Vg ⊆ Bε/3 (σg ). In particular, µ1 ∈ Uh ⇒ lossµ1 (h) < ε/3,

µ2 ∈ Vg ⇒ lossµ2 (g) < ε/3. (1)

(2)

(12) (1)

Choose partitions of unity subordinate to these covers, {fh }h∈{±1}X1 , {fg }g∈{±1}X2 , so that supp fh (2) Uh , supp fg ⊆ Vg , and

(1)

fh ≡ 1,

h∈{±1}X1

fg(2) ≡ 1.

g∈{±1}X2

We construct an (ε, L1 + L2 )-list-replicable learner for C1 ∗ C2 . Choose 0 < τ < ε/3 and a continuous cutoff function r : [0, 1] → [0, 1] such that r(s) = 0 for s ≤ τ /2,

r(s) = 1 for s ≥ τ.

⊆

Fix arbitrary default hypotheses h0 ∈ {±1}X1 and g0 ∈ {±1}X2 . Now choose arbitrary orderings {±1}X1 = {h1 , . . . , hM }, {±1}X2 = {g1 , . . . , gN } , where M = 2|X1 | and N = 2|X2 | . The hypotheses h0 and g0 may repeat some hi or gj ; this causes no difficulty, since lists are sets of hypotheses and repetitions can only decrease their size. Let µ ∈ ∆C1 ∗C2 . Write t := µ(X1 ) and 1 − t = µ(X2 ), and decompose µ = tµ1 + (1 − t)µ2 , where µi ∈ ∆Ci is the conditional distribution on Xi whenever the corresponding mass is nonzero. Define probability vectors p(µ) on {0, 1, . . . , M } and q(µ) on {0, 1, . . . , N } by (1)

p0 (µ) := 1 − r(t),

pi (µ) := r(t)fhi (µ1 )

(1 ≤ i ≤ M ),

and qj (µ) := r(1 − t)fg(2) (µ2 ) j

q0 (µ) := 1 − r(1 − t),

(1 ≤ j ≤ N ).

Let Pa (µ) :=

a X

Qb (µ) :=

pi (µ),

i=0

b X

qj (µ),

j=0

with P−1 (µ) = Q−1 (µ) = 0. Define intervals Ia (µ) := [Pa−1 (µ), Pa (µ)]

(0 ≤ a ≤ M ),

Jb (µ) := [Qb−1 (µ), Qb (µ)]

(0 ≤ b ≤ N ).

and Finally define wa,b (µ) := |Ia (µ) ∩ Jb (µ)|. In particular, every wa,b is continuous on ∆C1 ∗C2 and M X N X

wa,b (µ) = 1.

a=0 b=0

Define the good list for µ by List(µ) := {ha ⊔ gb : wa,b (µ) > 0} , where ha means the default h0 when a = 0, and similarly gb means g0 when b = 0. Claim 7.3. For every µ ∈ ∆C1 ∗C2 , | List(µ)| ≤ L1 + L2 , and every hypothesis in List(µ) has µ-loss less than ε. Proof. Let m(µ) := | {a : pa (µ) > 0} |,

n(µ) := | {b : qb (µ) > 0} |.

For two interval partitions of [0, 1] with m(µ) and n(µ) positive-length intervals, the number of positive-length intersections is at most m(µ) + n(µ) − 1. Indeed, sweeping from left to right, the active pair changes only when one crosses an endpoint of one of the two partitions. If t ≥ τ , then p0 (µ) = 0 and at most L1 of the non-default pi (µ) are positive. If t ≤ τ /2, then p0 (µ) = 1. If τ /2 < t < τ , then at most L1 + 1 of the pi (µ)’s are positive. The same statements hold for q(µ) with

1 − t in place of t. Since τ < 1/3, the two transition regimes τ /2 < t < τ and τ /2 < 1 − t < τ cannot occur simultaneously. Hence | List(µ)| ≤ m(µ) + n(µ) − 1 ≤ L1 + L2 . Now take any glued hypothesis ha ⊔ gb in List(µ). Then pa (µ) > 0 and qb (µ) > 0. If a ̸= 0, then (1) fha (µ1 ) > 0, and therefore µ1 ∈ Uha ; by (12), lossµ1 (ha ) < ε/3. If a = 0, then p0 (µ) > 0, so r(t) < 1, and hence t < τ < ε/3. Similarly, if b ̸= 0, then lossµ2 (gb ) < ε/3, while if b = 0, then 1 − t < τ . The case a = b = 0 is impossible, since it would imply t < τ and 1 − t < τ < ε/3. Therefore lossµ (ha ⊔ gb ) = t lossµ1 (ha ) + (1 − t) lossµ2 (gb ) < ε/3 + ε/3 < ε. This proves the claim. We now define the learning rule. Algorithm 3 The join learning rule A 1: Sample S = (S1 , . . . , Sn ) ∼ µn . 2: Construct the empirical distribution µ b on (X1 ⊔ X2 ) × {±1}. 3: Compute the weights wa,b (b µ) for all 0 ≤ a ≤ M and 0 ≤ b ≤ N . 4: Output ha ⊔ gb with probability wa,b (b µ). It remains to show that for sufficiently large n, the output belongs to List(µ) with probability at least 1 − δ, uniformly over µ. For a fixed µ ∈ ∆C1 ∗C2 define X Fµ (ν) := wa,b (ν). 0≤a≤M, 0≤b≤N : ha ⊔gb ∈List(µ) /

This is the probability that the algorithm, when run with empirical distribution ν, outputs a hypothesis outside List(µ). Since the sum is finite and the functions wa,b are continuous, Fµ is continuous. Moreover, Fµ (µ) = 0. The compactness of ∆C1 ∗C2 implies the finite family of functions wa,b is uniformly equicontinuous. More explicitly, choose ρ > 0 so that each wa,b changes by at most δ/(2R) on ρ-balls, where R = (M + 1)(N + 1). Thus this ρ is independent of µ, and whenever dTV (ν, µ) < ρ, we have Fµ (ν) < δ/2. Since X1 ⊔ X2 is finite, standard uniform convergence of empirical distributions gives an n0 = n0 (ρ, δ, X1 , X2 ) such that for every realizable µ and every n ≥ n0 , PS∼µn [dTV (b µ, µ) < ρ] ≥ 1 − δ/2. Consequently, for every µ ∈ ∆C1 ∗C2 and n ≥ n0 , PS∼µn [A(S) ∈ / List(µ)] ≤ P [dTV (b µ, µ) ≥ ρ] + E Fµ (b µ)1{dTV (bµ,µ)<ρ} ≤ δ/2 + δ/2 = δ. Together with Claim 7.3, this shows that A is an (ε, L1 + L2 )-list-replicable learner for C1 ∗ C2 . Therefore lr(C1 ∗ C2 , ε) ≤ L1 + L2 = lr(C1 , ε/3) + lr(C2 , ε/3). Taking the supremum over ε > 0 proves the final assertion. 25

References [ABL+ 22] Noga Alon, Mark Bun, Roi Livni, Maryanthe Malliaris, and Shay Moran. Private and online learnability are equivalent. J. ACM, 69(4):Art. 28, 34, 2022. [AFR85] Noga Alon, Peter Frankl, and Vojtech Rödl. Geometrical realization of set systems and probabilistic communication complexity. In 26th Annual Symposium on Foundations of Computer Science, FOCS 1985, pages 277–280. IEEE Computer Society, 1985. [AMY16] Noga Alon, Shay Moran, and Amir Yehudayoff. Sign rank versus VC dimension. In Conference on Learning Theory, pages 47–80. PMLR, 2016. [AO07] Peter Auer and Ronald Ortner. A new PAC bound for intersection-closed concept classes. Machine Learning, 66(2):151–163, 2007. [Atm22] Aistis Atminas. Classes of graphs without star forests and related graphs. Discrete Mathematics, 345(12):113089, 2022. [BDE98] Shai Ben-David and Nadav Eiron. Self-directed learning and its relation to the VC-dimension and to teacher-directed learning. Machine Learning, 33(1):87–104, 1998. [BGH+ 23] Mark Bun, Marco Gaboardi, Max Hopkins, Russell Impagliazzo, Rex Lei, Toniann Pitassi, Satchit Sivakumar, and Jessica Sorrell. Stability is stable: Connections between replicability, privacy, and adaptive generalization. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, pages 520–527, 2023. [BGHH25] Ari Blondal, Shan Gao, Hamed Hatami, and Pooya Hatami. Stability and list-replicability for agnostic learners. In Conference on Learning Theory, pages 380––400. PMLR, 2025. [BHH+ 26a] Ari Blondal, Hamed Hatami, Pooya Hatami, Chavdar Lalov, and Sivan Tretiak. Borsuk-Ulam and replicable learning of large-margin halfspaces. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing, pages 529–540, 2026. [BHH+ 26b] Ari Blondal, Hamed Hatami, Pooya Hatami, Chavdar Lalov, and Sivan Tretiak. Simplicial Covering Dimension of Extremal Concept Classes. In Shubhangi Saraf, editor, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026), volume 362 of Leibniz International Proceedings in Informatics (LIPIcs), pages 22:1–22:24, Dagstuhl, Germany, 2026. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. [BHH+ 26c] Ari Blondal, Hamed Hatami, Pooya Hatami, Chavdar Lalov, and Sivan Tretiak. Tight list replicability bounds via a novel sphere covering theorem, 2026. arXiv:2606.06148. [BHQS21] Avrim Blum, Steve Hanneke, Jian Qian, and Han Shao. Robust learning under clean-label attack. In Conference on Learning Theory, pages 591–634. PMLR, 2021. [BLM20] Mark Bun, Roi Livni, and Shay Moran. An equivalence between private classification and online prediction. In IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 389–402, 2020. [CCH+ 24] Zachary Chase, Bogdan Chornomaz, Steve Hanneke, Shay Moran, and Amir Yehudayoff. Dual vc dimension obstructs sample compression by embeddings. In The Thirty Seventh Annual Conference on Learning Theory, pages 923–946. PMLR, 2024. [CCMW22] Jérémie Chalopin, Victor Chepoi, Shay Moran, and Manfred K Warmuth. Unlabeled sample compression schemes and corner peelings for ample and maximum classes. Journal of Computer and System Sciences, 127:1–28, 2022.

[CCMY24] Zachary Chase, Bogdan Chornomaz, Shay Moran, and Amir Yehudayoff. Local Borsuk-Ulam, stability, and replicability. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, page 1769–1780, New York, NY, USA, 2024. Association for Computing Machinery. [CLSW04] Péter Csorba, Carsten Lange, Ingo Schurr, and Arnold Wassmer. Box complexes, neighborhood complexes, and the chromatic number. Journal of Combinatorial Theory, Series A, 108(1):159– 168, 2004. [CMW25] Bogdan Chornomaz, Shay Moran, and Tom Waknine. Spherical dimension. In Nika Haghtalab and Ankur Moitra, editors, Proceedings of Thirty Eighth Conference on Learning Theory, volume 291 of Proceedings of Machine Learning Research, pages 1259–1313. PMLR, 30 Jun–04 Jul 2025. [CMY23] Zachary Chase, Shay Moran, and Amir Yehudayoff. Stability and Replicability in Learning. In IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 2430–2439. IEEE Computer Society, 2023. [Dar15] Malte Darnstädt. The optimal pac bound for intersection-closed concept classes. Information Processing Letters, 115(4):458–461, 2015. [DJ03] Victor Dalmau and Peter Jeavons. Learnability of quantified formulas. Theoretical Computer Science, 306(1-3):485–511, 2003. [DPVWV23] Peter Dixon, A. Pavan, Jason Vander Woude, and N. V. Vinodchandran. List and certificate complexities in replicable learning. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NeurIPS ’23, Red Hook, NY, USA, 2023. Curran Associates Inc. [EHKS23] Eric Eaton, Marcel Hussing, Michael Kearns, and Jessica Sorrell. Replicable reinforcement learning. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NeurIPS ’23. Curran Associates Inc., 2023. [EKK+ 23] Hossein Esfandiari, Alkis Kalavasis, Amin Karbasi, Andreas Krause, Vahab Mirrokni, and Grigoris Velegkas. Replicable bandits. In The Eleventh International Conference on Learning Representations, 2023. [EKM+ 23] Hossein Esfandiari, Amin Karbasi, Vahab Mirrokni, Grigoris Velegkas, and Felix Zhou. Replicable clustering. In Advances in Neural Information Processing Systems, volume 36, pages 39277–39320. Curran Associates, Inc., 2023. [FHV26] Florian Frick, Kaave Hosseini, and Aliaksei Vasileuski. A Z2 -topological framework for signrank lower bounds, 2026. arXiv:2604.01510. [For02] Jürgen Forster. A linear lower bound on the unbounded error probabilistic communication complexity. J. Comput. System Sci., 65(4):612–625, 2002. Special issue on complexity, 2001 (Chicago, IL). [FW95] Sally Floyd and Manfred Warmuth. Sample compression, learnability, and the VapnikChervonenkis dimension. Machine learning, 21(3):269–304, 1995. [Han16] Steve Hanneke. Refined error bounds for several learning algorithms. Journal of Machine Learning Research, 17(135):1–55, 2016. [Han24] Steve Hanneke. The star number and eluder dimension: Elementary observations about the dimensions of disagreement. In The Thirty Seventh Annual Conference on Learning Theory, pages 2308–2359. PMLR, 2024. 27

[HHP+ 22] Hamed Hatami, Pooya Hatami, William Pires, Ran Tao, and Rosie Zhao. Lower bound methods for sign-rank and their limitations. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022), pages 22–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2022. [HK07] Pinar Heggernes and Dieter Kratsch. Linear-time certifying recognition algorithms and forbidden induced subgraphs. Nordic J. Comput., 14(1-2):87–108, 2007. [HLW94] David Haussler, Nick Littlestone, and Manfred K Warmuth. Predicting {0, 1}-functions on randomly drawn points. Information and Computation, 115(2):248–292, 1994. [HSW90] David Helmbold, Robert Sloan, and Manfred K Warmuth. Learning nested differences of intersection-closed concept classes. Machine Learning, 5(2):165–196, 1990. [HY15] Steve Hanneke and Liu Yang. Minimax analysis of active learning. The Journal of Machine Learning Research, 16(1):3487–3602, 2015. [Ill78] Sören Illman. Smooth equivariant triangulations of G-manifolds for G a finite group. Mathematische Annalen, 233(3):199–220, October 1978. [KKL+ 24] Alkis Kalavasis, Amin Karbasi, Kasper Green Larsen, Grigoris Velegkas, and Felix Zhou. Replicable learning of large-margin halfspaces. In Proceedings of the 41st International Conference on Machine Learning, ICML’24. JMLR.org, 2024. [KKMV23] Alkis Kalavasis, Amin Karbasi, Shay Moran, and Grigoris Velegkas. Statistical indistinguishability of learning algorithms. In Proceedings of the 40th International Conference on Machine Learning, ICML’23. JMLR.org, 2023. [Kuh99] Christian Kuhlmann. On teaching and learning intersection-closed concept classes. In European Conference on Computational Learning Theory, pages 168–182. Springer, 1999. [KVYZ23] Amin Karbasi, Grigoris Velegkas, Lin Yang, and Felix Zhou. Replicability in reinforcement learning. Advances in Neural Information Processing Systems, 36:74702–74735, 2023. [LKFS22] Gene Li, Pritish Kamath, Dylan J Foster, and Nati Srebro. Understanding the eluder dimension. Advances in Neural Information Processing Systems, 35:23737–23750, 2022. [Lov78] László Lovász. Kneser’s conjecture, chromatic number, and homotopy. Journal of Combinatorial Theory, Series A, 25(3):319–324, 1978. [Mat03] Jiřı́ Matoušek. Using the Borsuk-Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry. Universitext. Springer, Berlin/Heidelberg, 2003. [Mil64] J. Milnor. On the Betti numbers of real varieties. Proc. Amer. Math. Soc., 15:275–280, 1964. [MM22] Maryanthe Malliaris and Shay Moran. The unstable formula theorem revisited via algorithms. arXiv preprint arXiv:2212.05050, 2022. [MP95] N. V. R. Mahadev and U. N. Peled. Threshold graphs and related topics, volume 56 of Annals of Discrete Mathematics. North-Holland Publishing Co., Amsterdam, 1995. [MSS23] Shay Moran, Hilla Schefler, and Jonathan Shafer. The bayesian stability zoo. Advances in Neural Information Processing Systems, 36:61725–61746, 2023. [MW16] Shay Moran and Manfred K Warmuth. Labeled compression schemes for extremal classes. In International Conference on Algorithmic Learning Theory, pages 34–49. Springer, 2016.

[MZ02] Jiri Matousek and Günter M Ziegler. Topological lower bounds for the chromatic number: A hierarchy. arXiv preprint math/0208072, 2002. [PS86] Ramamohan Paturi and Janos Simon. Probabilistic communication complexity. Journal of Computer and System Sciences, 33(1):106–123, 1986. [RR22] Joachim Rubinstein and Benjamin Rubinstein. Unlabelled sample compression schemes for intersection-closed classes and extremal classes. Advances in Neural Information Processing Systems, 35:13078–13090, 2022. [Rud87] Walter Rudin. Real and complex analysis. McGraw-Hill, Inc., 1987. [RVR13] Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. Advances in Neural Information Processing Systems, 26, 2013. [ST06] Gábor Simonyi and Gábor Tardos. Local chromatic number, Ky Fan’s theorem, and circular colorings. Combinatorica, 26(5):587–626, 2006. [STV09] Gábor Simonyi, Gábor Tardos, and Siniša Vrećica. Local chromatic number and distinguishing the strength of topological obstructions. Transactions of the American Mathematical Society, 361(2):889–908, 2009. [Tho65] René Thom. Sur l’homologie des variétés algébriques réelles. In Differential and Combinatorial Topology (A Symposium in Honor of Marston Morse), pages 255–265. Princeton Univ. Press, Princeton, N.J., 1965. [War68] Hugh E. Warren. Lower bounds for approximation by nonlinear manifolds. Trans. Amer. Math. Soc., 133:167–178, 1968.

Record · ID 282775 · SHA-256 d0679aff6c1941d2
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.