Elizabeth Yang

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2023-87

May 10, 2023

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2023/EECS-2023-87.pdf

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.

Advisors: Satish Rao

---

BibTeX citation:

@phdthesis{Yang:EECS-2023-87,
    Author= {Yang, Elizabeth},
    Title= {Geometry-Inspired Sampling Algorithms and Random Graphs},
    School= {EECS Department, University of California, Berkeley},
    Year= {2023},
    Month= {May},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2023/EECS-2023-87.html},
    Number= {UCB/EECS-2023-87},
    Abstract= {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.},
}

EndNote citation:

%0 Thesis
%A Yang, Elizabeth 
%T Geometry-Inspired Sampling Algorithms and Random Graphs
%I EECS Department, University of California, Berkeley
%D 2023
%8 May 10
%@ UCB/EECS-2023-87
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2023/EECS-2023-87.html
%F Yang:EECS-2023-87