Geometry-Inspired Sampling Algorithms and Random Graphs- [electronic resource]
Geometry-Inspired Sampling Algorithms and Random Graphs- [electronic resource]
- 자료유형
- 학위논문파일 국외
- 최종처리일시
- 20240214100448
- ISBN
- 9798380381086
- DDC
- 004
- 저자명
- Yang, Elizabeth.
- 서명/저자
- Geometry-Inspired Sampling Algorithms and Random Graphs - [electronic resource]
- 발행사항
- [S.l.]: : University of California, Berkeley., 2023
- 발행사항
- Ann Arbor : : ProQuest Dissertations & Theses,, 2023
- 형태사항
- 1 online resource(112 p.)
- 주기사항
- Source: Dissertations Abstracts International, Volume: 85-03, Section: B.
- 주기사항
- Advisor: Rao, Satish.
- 학위논문주기
- Thesis (Ph.D.)--University of California, Berkeley, 2023.
- 사용제한주기
- This item must not be sold to any third party vendors.
- 초록/해제
- 요약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.
- 일반주제명
- Computer science.
- 일반주제명
- Mathematics.
- 일반주제명
- Applied mathematics.
- 키워드
- Random graph
- 키워드
- Random walks
- 기타저자
- University of California, Berkeley Computer Science
- 기본자료저록
- Dissertations Abstracts International. 85-03B.
- 기본자료저록
- Dissertation Abstract International
- 전자적 위치 및 접속
- 로그인 후 원문을 볼 수 있습니다.