We study the list replicability number in the realizable PAC learning framework and prove that every concept class H over a countable domain with Littlestone dimension d and dual VC dimension v∗ satisfies
LR(H)≤2O(dmin{logd,v∗}).
This matches the worst-case lower bound of 2Ω(d) up to a logarithmic factor in the exponent and exponentially improves the previous best upper bound LR(H)≤22O(d) of Bun, Livni, and Moran [FOCS 2020]. Unlike earlier bounds of 2Oε(d2) for fixed accuracy ε>0 implied by the work of Ghazi, Golowich, Kumar, and Manurangsi [STOC 2021] and Lyu [STOC 2026], our bound is independent of ε. The 2O(dlogd) bound follows from a new inductive framework for bounding list replicability that builds on the recent notion of irreducibility from differentially private learning. The 2O(dv∗) bound follows from a simple globally stable learner that takes the majority vote of multiple empirical risk minimizers, with stability established using tools from stable regularity.
In recent years, list replicability has emerged as a framework for formalizing reproducibility in learning theory. A central question is how the required list size relates to the accuracy parameter and natural complexity measures of the hypothesis class. To achieve sharp bounds on list replicability, we prove a novel topological sphere covering theorem, derived from the Borsuk-Ulam theorem. Specifically, if the d-sphere is covered by open sets, each of which lies in an open hemisphere, then d+1 of these sets must have a common intersection. Using this result, we obtain a sharp bound on the relationship between list size and accuracy for VC classes. We also show that for large-margin half-spaces, provided the margin is not too large, the optimal list size equals the ambient dimension. However, when the margin is taken to be very large, we devise a replicable algorithm achieving the minimal list size of ⌈d/2⌉+1.
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.
Zhang [Zha26] recently posted a manuscript announcing that the list-replicability number of every class of M≥2 binary concepts on N≥2 domain points is O(log2MlogN), which would be the first polylogarithmic upper bound on this quantity. In this note, we present a short, self-contained proof of this bound, following the high-level approach of the manuscript but with considerably simpler arguments.