Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces
Abstract
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.
Fields of Study & Subjects
Complexity and Algorithms in Graphs
Advanced Graph Theory Research
Topological and Geometric Data Analysis
Publication details
- Journal / source
- Proceedings of the 58th Annual ACM Symposium on Theory of Computing
- Publisher
- ACM
- Pages
- 529–540
- Publication date
- 9 June 2026
- Language
- EN