백석예술대학교 도서관

내용보기

Geometry-Inspired Sampling Algorithms and Random Graphs- [electronic resource]

서명/저자: Geometry-Inspired Sampling Algorithms and Random Graphs - [electronic resource]

주기사항: Source: Dissertations Abstracts International, Volume: 85-03, Section: B.

초록/해제: 요약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.