11 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…
John Ellipsoids of Revolution
Grigory Ivanov, Zsolt Lángi, Márton Naszódi +1
Finding a largest Euclidean ball in a given convex body and finding a largest volume ellipsoid in are two problems of fundamentally different nature. T…
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…
Helly numbers for Quantitative Helly-type results
G. Ivanov, M. Naszodi
We obtain three Helly-type results. First, we establish a Quantitative Colorful Helly-type theorem with the optimal Helly number \(2d\) concerning the diameter of the intersection…
No-dimensional Helly's theorem in uniformly convex Banach spaces
G. Ivanov
We study the ``no-dimensional'' analogue of Helly's theorem in Banach spaces. Specifically, we obtain the following no-dimensional Helly-type results for uniformly convex Banach sp…
Tight colorful no-dimensional Tverberg theorem
Polina Barabanshchikova, Grigory Ivanov, Alexander Polyanskii
We study colorful no-dimensional Tverberg-type problems and obtain several optimal results. A colorful no-dimensional Tverberg-type theorem provides a bound on a radius such th…
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 .…
Quantitative Steinitz theorem and polarity
Grigory Ivanov
The classical Steinitz theorem asserts that if the origin lies within the interior of the convex hull of a set , then there are at most points in w…