4 papers · 1 filter
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 concept…
Greedy sparsifications of sums of positive semidefinite matrices
Grigory Ivanov
We prove a deterministic analogue of Rudelson's sampling theorem for sums of positive semidefinite matrices. Let be positive semidefinite \(d\times d\) matrices, an…
On Banach Spaces with the Helly Approximation Property
Grigory Ivanov
Qualitatively, a no-dimensional Helly-type theorem says that if every small subfamily of convex sets has a common point in a bounded region, then suitable neighborhoods of all the…
No-dimensional results of combinatorial convexity. Dimension strikes back
Grigory Ivanov
We discuss no-dimensional (approximate) versions of Carathéodory's and Helly's theorems. Our goal is to draw attention to open problems and potential applications related to these…