Sign-Rank, Index, and List Replicability: Connections and Separations
English summary
This paper studies three complexity measures for binary concept classes in learning theory: sign rank, Z₂-index, and list replicability number. It proves that the Z₂-index is bounded above by a linear function of the list replicability number, establishing list replicability as the stronger of the two lower bounds. Using this relationship, the authors obtain a strong separation between sign rank and Z₂-index, resolving a question of Frick, Hosseini, and Vasileuski. Additionally, upper bounds on list replicability are given via the combinatorial measures height and minimum star number, and a composition theorem shows the list replicability number of a product class is at most the sum of the individual numbers.
Chinese summary
本文研究了学习理论中二元概念类的三个复杂度度量：符号秩、Z₂-指标和列表可复现数。证明了Z₂-指标不超过列表可复现数的线性函数，说明列表可复现性是这两个下界中更强的一个。基于这一关系，作者得到了符号秩与Z₂-指标的强分离，解决了Frick、Hosseini和Vasileuski提出的问题。此外，还通过高度和最小星数这两个组合度量给出了列表可复现数的上界，并证明了一个组合定理：两个概念类的乘积的列表可复现数不超过各自列表可复现数之和。
Key points
Proves Z₂-index ≤ O(list replicability number), establishing list replicability as a stronger lower bound for sign rank.
证明Z₂-指标 ≤ 线性(列表可复现数)，从而列表可复现性是符号秩更强的一个下界。
Obtains a strong separation between sign rank and Z₂-index, resolving an open problem of Frick, Hosseini, and Vasileuski.
得到了符号秩与Z₂-指标的强分离，解决了Frick、Hosseini和Vasileuski提出的开放问题。
Derives upper bounds on list replicability using the combinatorial measures height and minimum star number.
利用高度和最小星数这两个组合度量导出列表可复现数的上界。
Shows that the list replicability number of a product of two concept classes is at most the sum of their list replicability numbers.
证明两个概念类乘积的列表可复现数不超过各自列表可复现数之和。