The logarithmic list-replicability conjecture for sign matrices

Let AA be an N×MN \times M sign matrix, and let \textsclr(A)\operatorname{\textnormal{\textsc{lr}}}(A) denote its list replicability number. List-replicability conjecture. Every N×MN \times M sign matrix AA satisfies

\textsclr(A)=O(logNlogM).\operatorname{\textnormal{\textsc{lr}}}(A) = O(\log N \log M).

The conjecture asserts that list replicability is at most logarithmic in each matrix dimension. Originally posed in, it was resolved for extremal concept classes in, where \textsclr(C)=Θ(\textscvc(C))\operatorname{\textnormal{\textsc{lr}}}(\mathcal{C}) = \Theta(\operatorname{\textnormal{\textsc{vc}}}(\mathcal{C})) was shown.

Sources & referencesView supporting material

Primary source

Ari Blondal, Hamed Hatami, Pooya Hatami, Chavdar Lalov and Sivan Tretiak, “Sign-Rank, Index, and List Replicability: Connections and Separations”, arXiv:2606.18236 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.