Zhang [Zha26] recently posted a manuscript announcing that the list-replicability number of every class of M\ge 2 binary concepts on N\ge 2 domain points is O(\log^2 M\log N), 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.
A polylogarithmic bound for list replicability
Zhang [Zha26] recently posted a manuscript announcing that the list-replicability number of every class of $M\ge 2$ binary concepts on $N\ge 2$ domain points is $O(\log^2 M\log N)$, which would be the first polylogarithmic upper bound on this quantity.
- Preview
- Year
- 2026
- Hosting
- Excerpt onlyCC-BY-NC-SA-4.0
Cite
Notes
Only stored in your browser.
Attribution
- Abstract & full text
- arxiv.org/abs/2610.20657CC-BY-NC-SA-4.0
- TL;DR
- Semantic Scholar