2026-07-24T02:00:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25309 2026-03-19T13:03:18Z ddc:004 open_access

Simplicial Covering Dimension of Extremal Concept Classes Blondal, Ari Hatami, Hamed Hatami, Pooya Lalov, Chavdar Tretiak, Sivan PAC Learning Extremal Concept Classes Replicability List Replicability Topology Geometry Dimension theory is a branch of topology concerned with defining and analyzing dimensions of geometric and topological spaces in purely topological terms. In this work, we adapt the classical notion of topological dimension (Lebesgue covering) to binary concept classes. The topological space naturally associated with a concept class is its space of realizable distributions. The loss function and the class itself induce a simplicial structure on this space, with respect to which we define a simplicial covering dimension. We prove that for finite concept classes, this simplicial covering dimension exactly characterizes the list replicability number (equivalently, global stability) in PAC learning. This connection allows us to apply tools from classical dimension theory to compute the exact list replicability number of the broad family of extremal concept classes. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ari Blondal and Hamed Hatami and Pooya Hatami and Chavdar Lalov and Sivan Tretiak 2026 Is Part Of LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2026.22 urn:nbn:de:0030-drops-253094 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.22 eng https://creativecommons.org/licenses/by/4.0/legalcode