精选理由
这篇论文厘清了信号秩、Z2-索引和列表可复制数三个复杂概念的关系，解决了前人遗留的分离问题，还给出了组合上界，适合对学习理论下界感兴趣的人。
这篇论文研究了二元概念类的信号秩（sign rank）的下界方法。作者证明了Z2-索引（Z2-index）被列表可复制数（list replicability number）的线性函数所上界，从而解决了Frick、Hosseini和Vasileuski提出的信号秩与Z2-索引之间是否存在强分离的问题。论文进一步分析了列表可复制数的上界，将其关联到两个组合度量：高度（height）和最小星数（minimum star number）。最后，作者证明了两个概念类的乘积的列表可复制数不超过各自列表可复制数之和。
AI 翻译 · 中文
这篇论文研究了二元概念类的信号秩（sign rank）的下界方法。作者证明了Z2-索引（Z2-index）被列表可复制数（list replicability number）的线性函数所上界，从而解决了Frick、Hosseini和Vasileuski提出的信号秩与Z2-索引之间是否存在强分离的问题。论文进一步分析了列表可复制数的上界，将其关联到两个组合度量：高度（height）和最小星数（minimum star number）。最后，作者证明了两个概念类的乘积的列表可复制数不超过各自列表可复制数之和。
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 …