cs.LGNov 7, 2026

Sharp Logarithmic-Product Bounds for List Replicability of Sign Matrices

Authors: Guangjian Zhang

Abstract

List replicability measures how many accurate hypotheses suffice to contain the output of a learning rule with arbitrarily high confidence. We prove that every nonempty class of mm binary concepts on nn domain points has list replicability at most 805ln⁡(2m)ln⁡(2n)805\ln(2m)\ln(2n). This resolves the logarithmic-product conjecture of Blondal, Hatami, Hatami, Lalov, and Tretiak. Hanner matrices give lower bounds of the same order, for square matrices and for explicit families with unequal logarithmic aspect ratios. The upper bound is obtained by constructing nested acyclic sets in the faces of a cube. A critical-point estimate supplies highly connected regions, weighted cell attachments keep the sets compatible across faces, and a cubical carrier theorem converts them into accurate finite covers and learning rules. Appending one constant coordinate turns list replicability into an exact geometric quantity, the face width, and graph-orientation classes satisfy exact product formulas. In particular, there are explicit classes with list replicability 4k+14k+1 and equivariant index 3k3k, so the additive gap between the two is unbounded. We also develop entropy-tilting and two-sided Gibbs constructions, give combinatorial upper bounds adapted to structured matrices, compute exact values on classical families, and study the index of Paley matrices.

Figures & tables

Explore similar work

CardsList
  1. A polylogarithmic bound for list replicability

    Oct 14, 2026Ari Blondal, Hamed Hatami, Pooya Hatami +2Concept Learning

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

    Jun 16, 2026Ari Blondal, Hamed Hatami, Pooya Hatami +2Statistical Learning Theory

  3. Near-Optimal List Replicability from Littlestone Dimension

    Oct 23, 2026Ari Blondal, Pooya Hatami, Chavdar Lalov +1PAC Learning