Id: arxiv/2611.10408 Url: https://arxiv.org/abs/2611.10408 Tags: cs.LG, math.CO Score: 0 Title: Sharp Logarithmic-Product Bounds for List Replicability of Sign Matrices Domain: cs.LG Source: arxiv Authors: Guangjian Zhang Reviews: 0 Subject: cs.LG Category: research Comments: 0 Disputed: false Division: cs Mentions: 0 Discussed: 0 Published: 2026-11-07 Page: https://delphi.science/r/arxiv/2611.10408 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 $m$ binary concepts on $n$ domain points has list replicability at most $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…