揭示符号秩与列表可复现性之间的关系，解决了一个长期悬而未决的理论问题。
Sign-Rank, Index, and List Replicability: Connections and Separations
- 通过组合分析建立列表可复现性上界，关联高度与最小星数等组合性质。
- 证明列表可复现性在乘积概念类中具有可加性，为复杂度分析提供工具。
- 首次明确区分符号秩与Z2-指标的差距，推动学习理论下界研究进展。
在学习理论中，二元概念类的符号秩表示其能被点与半空间表示的最小维度。尽管备受关注，符号秩的下界极难获得。近期两种新方法分别利用更易分析的Z2-指标和列表可复现性数来推导符号秩下界。本文对这些度量进行排序，证明Z2-指标受列表可复现性数的线性上界控制。作为主要结果，我们得到了符号秩与Z2-指标之间的强分离，从而解决了Frick、Hosseini和Vasileuski提出的问题。这促使我们深入研究更强的下界度量——列表可复现性。我们通过高和最小星数两个组合度量建立了列表可复现性的上界，并证明了基本的复合性结果：两个概念类的乘积的列表可复现性数不超过二者之和。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。