PreprintCC BY-NC-SA 4.0arXiv
A polylogarithmic bound for list replicability
Abstract
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(log2 Mlog 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.
Related
- Polylogarithmic bound for the Gyárfás-Sumner conjecture
- A Generalized Half-Singleton Bound for List Decoding of Insertion/Deletion Errors
- An Improved Johnson Bound for List-Decoding with Hints
- Constant-List Insertion--Deletion Codes:New Bounds and an Improvement of Levenshtein's Lower Bound
- Abelian Cayley High-Dimensional Expanders with Polylogarithmic Degree
BibTeX
@misc{blondal2026polylogarithmic,
title = {{A polylogarithmic bound for list replicability}},
author = {Ari Blondal and Hamed Hatami and Pooya Hatami and Chavdar Lalov and Sivan Tretiak},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.20657},
eprint = {2610.20657},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.20657},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - A polylogarithmic bound for list replicability
AU - Ari Blondal
AU - Hamed Hatami
AU - Pooya Hatami
AU - Chavdar Lalov
AU - Sivan Tretiak
PY - 2026
DA - 2026/10/14
PB - arXiv
DO - 10.48550/arxiv.2610.20657
UR - https://arxiv.org/abs/2610.20657
AB - 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(log^2 Mlog 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.
ER -