2024 Theses Doctoral

A Complexity-Theoretic Perspective on Convex Geometry

Nadimpalli, Shivam

This thesis considers algorithmic and structural aspects of high-dimensional convex sets with respect to the standard Gaussian measure.

Among our contributions, (i) we introduce a notion of "influence" for convex sets that yields the first quantitative strengthening of Royen's celebrated Gaussian correlation inequality; (ii) we investigate the approximability of general convex sets by intersections of halfspaces, where the approximation quality is measured with respect to the standard Gaussian distribution; and (iii) we give the first lower bounds for testing convexity and estimating the distance to convexity of an unknown set in the black-box query model.

Our results and techniques are inspired by a number of fundamental ingredients and results---such as the influence of variables, noise sensitivity, and various extremal constructions---from the analysis of Boolean functions in complexity theory.