On random diameters of convex bodies

Source abstract

Let $K \subset \mathbb{R}^N$ be a convex body containing the origin in its interior. In this work, we study the diameters of random sections of $K$ and derive upper and lower bounds for them in terms of geometric parameters of $K$. Our bounds hold with large probability, and they offer new insights into this widely studied subject. Our upper bound complements the so-called low $M^*$-estimate and in many cases it is much sharper. The two lower bounds that we give are each of a different nature: depending on the body in question each time, either could be better, and in many interesting cases it matches the upper bound too. Subsequently, we apply our results to determine random diameters of $p$-ellipsoids (images of $\ell_p$ balls under diagonal operators), improving upon previously known results and achieving sharp estimates in many cases. One notable application is to Information-Based Complexity Theory, where we manage to establish a simple (and essentially optimal) dichotomy in response to a very natural conjecture posed by Hinrichs, Prochno and Sonnleitner in 2023. Our solution settles precisely when it is useful to replace the optimal information used for the recovery of vectors from a $p$-ellipsoid with random (Gaussian) information, which can be more practical to obtain.