UC Berkeley

High-dimensional expansion, a generalization of graph expansion to higher-order edges, has recently garnered significant attention in the theoretical computer science community for the additional boost they give in applications like error-correction and approximate sampling. In this thesis, we explore two problems related to high-dimensional expansion, using tools from the geometry of polynomials as well as high-dimensional convex geometry.

First, we study approximate sampling from discrete distributions. The framework for sampling obtained from high-dimensional expansion provides both a natural set of random walks to use in MCMC algorithms, as well as a set of tools for their analysis. We show that the geometric properties (e.g. log-concavity) of a polynomial derived from the distribution allows us to speed up the implementations of these random walks.

Next, we study a random graph model called the ``random geometric graph,'' with an eventual goal of understanding its modeling capabilities as well as its high-dimensional expansion properties. Along the way, we prove new results about distinguishing the random geometric graph model from the Erdos-Renyi model, and develop a new geometric toolkit for analyzing these graphs.