9 papers
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…
The John inclusion for log-concave functions
G. Ivanov
John's inclusion states that a convex body in can be covered by the -dilation of its maximal volume ellipsoid. We obtain a certain John-type inclusion for log-con…
Colorful positive bases decomposition and Helly-type results for cones
Grigory Ivanov
We prove the following colorful Helly-type result: Fix . Assume are finite sets (colors) of nonzero vectors in .…