자료유형  

 학위논문

Control Number  

0016934795

International Standard Book Number  

9798380366212

Dewey Decimal Classification Number  

004

Main Entry-Personal Name  

Liu, Siqi.

Publication, Distribution, etc. (Imprint  

[S.l.] : University of California, Berkeley., 2023

Publication, Distribution, etc. (Imprint  

Ann Arbor : ProQuest Dissertations & Theses, 2023

Physical Description  

1 online resource(155 p.)

General Note  

Source: Dissertations Abstracts International, Volume: 85-03, Section: B.

General Note  

Advisor: Chiesa, Alessandro.

Dissertation Note  

Thesis (Ph.D.)--University of California, Berkeley, 2023.

Restrictions on Access Note  

This item must not be sold to any third party vendors.

Summary, Etc.  

요약Expanders are well-connected graphs. They have numerous applications in constructions of error correcting codes, metric embedding, derandomization, sampling algorithms, etc. Local-spectral expanders (HDXes) are a generalization of expander graphs to hypergraphs. They have recently received more attention due to their applications to agreement tests, locally testable codes, hardness of SoS refutation, and connections with local sampling algorithms. In comparison to expanders we have very limited understanding of HDXes: there are abundant random or explicit constructions of sparse expander graphs such as random d-regular graphs, algebraic expanders, the zig-zag product, etc. In contrast, we know only two general constructions of sparse HDXes: the LSV complexes [90] and the coset construction. In this thesis, we take two approaches to tackle the construction problem. The first approach is taking graph products of sparse expander graphs. This is inspired by the zig-zag product. However, this construction fails to give good local-spectral expansion. The second approach is inspired by the following question: does any continuous space have the local-spectral expansion property? We show that the answer is affirmative for high-dimensional spheres. More precisely, we show that 3-uniform hypergraphs sampled randomly over high-dimensional spheres are (relatively sparse) local-spectral expanders.Furthermore, tight isoperimetric inequalities of local-spectral expanders have remained elusive. Intuitively, isoperimetric inequalities provide a lower bound on the probability that a random walk leaves a subset of vertices in the graph. A tight bound on this probability is crucial for applications to agreement testing. In this thesis, we explore this problem and give an improved bound for good local-spectral expanders.

Subject Added Entry-Topical Term  

Computer science.

Subject Added Entry-Topical Term  

Statistical physics.

Subject Added Entry-Topical Term  

Mathematics.

Index Term-Uncontrolled  

High dimensional expanders

Index Term-Uncontrolled  

Hypercontractivity

Index Term-Uncontrolled  

Local-spectral expanders

Index Term-Uncontrolled  

Random geometric graphs

Index Term-Uncontrolled  

Small set expansion

Added Entry-Corporate Name  

University of California, Berkeley Electrical Engineering & Computer Sciences

Host Item Entry  

Dissertations Abstracts International. 85-03B.

Host Item Entry  

Dissertation Abstract International

Electronic Location and Access  

로그인을 한후 보실 수 있는 자료입니다.

Control Number  

joongbu:640945