Sign-Rank, Index, 그리고 List Replicability: 연결성과 분리성

학습 이론(learning theory)에서, 이진 개념 클래스(binary concept class)의 sign rank는 점(points)과 반공간(halfspaces)으로 표현될 수 있는 가장 작은 차원을 포착합니다. 엄청난 관심에도 불구하고, sign rank에 대한 하한(lower bounds)을 구하는 것은 매우 어려운 것으로 알려져 있습니다. 이 문제에 대한 두 가지 최근 접근 방식은 분석하기 더 쉬운 척도인 $\mathbb{Z}_2$-index와 list replicability number를 통해 sign rank의 하한을 설정합니다. 우리는 이러한 척도들의 순서를 정하며, $\mathbb{Z}_2$-index가 list replicability number의 선형 함수에 의해 상한(upper-bounded)이 됨을 보여줍니다. 주요 결과로서, 우리는 sign rank와 $\mathbb{Z}_2$-index 사이의 강력한 분리(separation)를 얻었으며, 이를 통해 Frick, Hosseini, 그리고 Vasileuski의 질문을 해결합니다. 이는 두 가지 하한 척도 중 더 강력한 list replicability에 대한 철저한 연구를 촉발합니다. 우리는 두 가지 조합론적 척도인 height와 minimum star number를 통해 list replicability number의 상한을 설정합니다. 또한, 두 개념 클래스의 곱(product)이 각 클래스의 list replicability number의 합에 의해 제한되는 list replicability number를 가진다는 근본적인 합성(composition) 결과를 증명합니다.