AF: Small: Randomness Extraction and Pseudorandomness

点击翻译按钮获取中文摘要

Random numbers are surprisingly useful in computer science. For example, they are used for simulations of complex systems, such as the weather and the economy. In addition, randomness is essential for "streaming algorithms," where there is so much data arriving that it is impossible to store it all. Moreover, randomness is vital for computer security. While randomness has many applications, truly random numbers are difficult to obtain. It is therefore important to develop techniques to get by with less randomness or lower quality randomness. The main tool to reduce the amount of randomness required is a pseudorandom number generator. In contrast, the main tool to reduce the quality of randomness required is a randomness extractor.This proposal addresses important questions about pseudorandom generators and randomness extractors that relate to the investigator's recent work. For example, the investigator and his student gave an efficient algorithm that extracts randomness from two independent sources of low-quality randomness that was dramatically better than previously known. However, the error is too large for applications in cryptography. The investigator proposes to improve this, as well as work on other aspects of randomness extraction. The investigator also proposes to construct pseudorandom generators that work for large classes of randomized algorithms, such as those using a small amount of memory. Finally, the investigator proposes work connecting these objects to seemingly unrelated areas, such as big data in the form of streaming algorithms.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.