자료유형  

 학위논문

Control Number  

0017161263

International Standard Book Number  

9798382841045

Dewey Decimal Classification Number  

004

Main Entry-Personal Name  

Liao, Jyun-Jie.

Publication, Distribution, etc. (Imprint  

[S.l.] : Cornell University., 2024

Publication, Distribution, etc. (Imprint  

Ann Arbor : ProQuest Dissertations & Theses, 2024

Physical Description  

223 p.

General Note  

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

General Note  

Advisor: Chattopadhyay, Eshan.

Dissertation Note  

Thesis (Ph.D.)--Cornell University, 2024.

Summary, Etc.  

요약Randomness is a powerful resource in computer science, with rich applications in algorithm design, cryptography, distributed computing, etc. Most of the applications assume access to a sequence of uniform and independent random bits. However, the randomness we collect from nature (e.g., activity of CPU, atmospheric noise, radioactive decay) does not seem as perfect. This motivates the study of randomness extractors, which are deterministic algorithms that can convert an imperfect random source (with some entropy) into a uniform random string. The ultimate goal in the area of randomness extraction is to construct an extractor that can work for any source that we would ever see in nature and applications. Unfortunately, a folklore result shows that it is impossible to construct an extractor that can work for every source that has entropy. It is therefore necessary to assume that the given source has certain structure, but we still hope that the structure we assume is as general as possible. In this thesis, we first focus on the construction of randomness extractors for sources with additive structure. This includes affine sources, which are uniform distributions over affine subspaces; and more generally the sum of two independent sources, which is a surprisingly general model that contains many other natural sources such as independent sources, affine sources and sources samplable by space-bounded computation. For both models, we construct extractors that improve the previous state-of-the-art, and develop many useful tools along the way. In addition, we discover new connections between sources with additive structure and space-bounded computation, and as a result we obtain extractors for small-space sources with optimal entropy requirement, and a new lower bound for linear branching programs. Finally, we develop more results regarding randomness and space-bounded computation, including new weighted pseudorandom generators and derandomization bounds for small-space algorithms.

Subject Added Entry-Topical Term  

Computer science.

Subject Added Entry-Topical Term  

Computer engineering.

Subject Added Entry-Topical Term  

Applied mathematics.

Index Term-Uncontrolled  

Derandomization

Index Term-Uncontrolled  

Pseudorandom generator

Index Term-Uncontrolled  

Randomness extractor

Index Term-Uncontrolled  

Space-bounded computation

Index Term-Uncontrolled  

Sumset extractors

Added Entry-Corporate Name  

Cornell University Computer Science

Host Item Entry  

Dissertations Abstracts International. 85-12B.

Electronic Location and Access  

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

Control Number  

joongbu:658477