Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces

We prove that the list replicability number of d-dimensional γ-margin half-spaces satisfies d/2+1 ≤ LR(Hγd) ≤ d. In particular, it grows with the dimension. Our lower bound uses a topological argument based on a local Borsuk–Ulam theorem. Our upper bound is proved by constructing a list-replicable learning rule from the generalization properties of SVMs. These bounds yield several consequences in learning theory and communication complexity. In learning theory, we show that every disambiguation of infinite-dimensional large-margin half-spaces to a total concept class has unbounded Littlestone dimension, answering a question of Alon, Hanneke, Holzman, and Moran (FOCS 2021). We also show that the maximum list-replicability number of any finite set of points and homogeneous half-spaces in ℝd is d, resolving a problem of Chase, Moran, and Yehudayoff (FOCS 2023). In addition, we construct a partial concept class with Littlestone dimension 1 such that all its disambiguations have infinite Littlestone dimension, resolving a problem of Cheung, H. Hatami, P. Hatami, and Hosseini (ICALP 2023). In communication complexity, we prove that every disambiguation of Gap Hamming Distance in the large-gap regime has unbounded public-coin randomized communication complexity, answering a question of Fang, Göös, Harms, and Hatami (STOC 2025). We also obtain an O(1) versus ω(1) separation between randomized and pseudo-deterministic communication complexity.