서브메뉴
검색
Geometry-Inspired Sampling Algorithms and Random Graphs- [electronic resource]
![Geometry-Inspired Sampling Algorithms and Random Graphs - [electronic resource]](/Users/Baul/Images/book.png)
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
- 전자적 위치 및 접속
- 로그인 후 원문을 볼 수 있습니다.
MARC
008240612s2023 us |||||||||||||||c||eng d■001000016932362
■00520240214100448
■006m o d
■007cr#unu||||||||
■020 ▼a9798380381086
■035 ▼a(MiAaPQ)AAI30491848
■040 ▼aMiAaPQ▼cMiAaPQ
■0820 ▼a004
■1001 ▼aYang, Elizabeth.
■24510▼aGeometry-Inspired Sampling Algorithms and Random Graphs▼h[electronic resource]
■260 ▼a[S.l.]:▼bUniversity of California, Berkeley. ▼c2023
■260 1▼aAnn Arbor :▼bProQuest Dissertations & Theses, ▼c2023
■300 ▼a1 online resource(112 p.)
■500 ▼aSource: Dissertations Abstracts International, Volume: 85-03, Section: B.
■500 ▼aAdvisor: Rao, Satish.
■5021 ▼aThesis (Ph.D.)--University of California, Berkeley, 2023.
■506 ▼aThis item must not be sold to any third party vendors.
■520 ▼aHigh-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.
■590 ▼aSchool code: 0028.
■650 4▼aComputer science.
■650 4▼aMathematics.
■650 4▼aApplied mathematics.
■653 ▼aHigh-dimensional expansion
■653 ▼aHigh-dimensional geometry
■653 ▼aRandom graph
■653 ▼aGeometric properties
■653 ▼aRandom walks
■690 ▼a0984
■690 ▼a0405
■690 ▼a0364
■71020▼aUniversity of California, Berkeley▼bComputer Science.
■7730 ▼tDissertations Abstracts International▼g85-03B.
■773 ▼tDissertation Abstract International
■790 ▼a0028
■791 ▼aPh.D.
■792 ▼a2023
■793 ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T16932362▼nKERIS▼z이 자료의 원문은 한국교육학술정보원에서 제공합니다.
■980 ▼a202402▼f2024
