这篇论文厘清了信号秩、Z2-索引和列表可复制数三个复杂概念的关系，解决了前人遗留的分离问题，还给出了组合上界，适合对学习理论下界感兴趣的人。
这篇论文研究了二元概念类的信号秩（sign rank）的下界方法。作者证明了Z2-索引（Z2-index）被列表可复制数（list replicability number）的线性函数所上界，从而解决了Frick、Hosseini和Vasileuski提出的信号秩与Z2-索引之间是否存在强分离的问题。论文进一步分析了列表可复制数的上界，将其关联到两个组合度量：高度（height）和最小星数（minimum star number）。最后，作者证明了两个概念类的乘积的列表可复制数不超过各自列表可复制数之和。
Sign-Rank, Index, and List Replicability: Connections and Separations
In learning theory, the sign rank of a binary concept class captures the smallest dimension in which it can be represented by points and halfspaces. Despite tremendous interest, lower bounds on sign rank are notoriously difficult to come by. Two recent approaches to the problem establish lower bounds on sign rank by measures that are easier to analyze: the $\mathbb{Z}_2$-index and the list replicability number. We order these measures, showing that the $\mathbb{Z}_2$-index is upper-bounded by a linear function of the list replicability number. As a main consequence, we obtain a strong separation between sign rank and $\mathbb{Z}_2$-index, thereby resolving a question of Frick, Hosseini, and Vasileuski. This motivates a thorough study of list replicability, the stronger of the two lower-bounding measures. We establish upper bounds on the list replicability number by two combinatorial measures: height and minimum star number. We also prove a fundamental composition result, showing that the product of two concept classes has list replicability number bounded by the sum of the list replicability numbers of the two classes.