Back to search

Cornell University

Extractors for Additive Structures and Space-bounded Computation

Abstract

dc:description.abstract

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, ra-dioactive 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.

Degree

thesis:*
Name thesis:degree_name
Ph. D., Computer Science
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Computer Science
Grantor
Cornell University
Year dc:date.issued
2024

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Liao, Jyun-Jie
Chair dc:contributor.chair
  • Chattopadhyay, Eshan
Committee members dc:contributor.committeemember
  • Kleinberg, Robert
  • Shi, Runting

Subjects

dc:subject × 5

Rights

dc:rights
Statement dc:rights
  • Attribution 4.0 International
Language dc:language.iso
en

Identifiers

dc:identifier.*
Dc Identifier Bibid
16575475
Dc Identifier Other
ProQuest Submission ID: 14234
ProQuest Publication ID: 31241126

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Liao, Jyun-Jie. Extractors for Additive Structures and Space-bounded Computation. Doctor of Philosophy thesis, Cornell University, 2024. https://hdl.handle.net/1813/115952