•  
  •  
 

Abstract

Randomness is crucial to computer science, both in theory and applications. In complexity theory, randomness augments computers to offer more powerful models. In cryptography, randomness is essential for seed generation, where the computational model used is generally probabilistic. However, ideal randomness, which is usually assumed to be available in computer science theory and applications, might not be available to real systems. Randomness extractors are objects that turn “weak” randomness into almost “ideal” randomness (pseudorandomness). In this paper, we will build the framework to work with such objects and present explicit constructions. We will discuss a well-known construction of seeded extractors via universal hashing and present a simple argument to extend such results to two-source extractors.

Author Bio

In December of 2015, Wei Dai finished his BS degrees in Mathematics and Computer Science in the College of Creative Studies at University of California, Santa Barbara. He is currently preparing to defend his Master Thesis at UCSB. He will start his PhD studies in Computer Science at the University of California, San Diego this fall.

Download

Share

COinS