Márton Naszódi

The VC dimension of partial concept classes via Radon's theorem

Grigory Ivanov, Attila Jung, Márton Naszódi

Following Alon, Hanneke, Holzman, and Moran (FOCS 2021), we define a partial concept class (PCC) as a family of partial functions \(f: V\to\{0,1,\ast\}\); equivalently, its concepts partition the ground set into black ($f^{-1}(1)$), grey ($f^{-1}(\ast)$), and white parts ($f^{-1}…Read more