CAREER: Randomness in Computation

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

The use of randomness is ubiquitous in computation, with applications ranging in many areas such as algorithm design, cryptography, and distributed computing. While in some areas, such as cryptography, not much can be done without randomness, in other areas such as algorithm design, it is not clear if there is a fundamental reason that randomness should be useful. Further, in applications where randomness is crucially important, it is often the case that one needs access to purely random bits but natural sources of randomness are typically defective. Thus, while many applications heavily rely on randomized techniques, there are many important questions related to the power and requirement of randomness, as well producing high quality randomness that we still do not understand. The major research agenda of this project is to further our understanding on these broad directions (which are central questions in the area of pseudo-randomness) using exciting recent progress. The project also features activities designed to increase the fraction of undergraduates from disadvantaged backgrounds choosing computer science as a major.The main research goals of this project can be broadly classified into the following two directions: (i) Unconditional de-randomization: A central question in complexity theory is if randomness is necessary in efficient computation. There are longstanding conjectures and conditional results that indicate that one can derandomize efficient computation (i.e., remove the use of randomness without paying much in efficiency). A central goal of this project is to push the state-of-art in several important directions that include (unconditionally) derandomizing algorithms that use limited memory, and various sorts of circuit families that have been beyond reach so far. The investigator plans to tackle these problems by leveraging multiple new approaches that have surfaced recently such as exploiting Fourier analytic structure, and new frameworks of de-randomization based on recent notions such as fractional pseudorandom generators, and pseudorandom pseudo-distributions. (ii) Extracting pure random bits from defective sources of randomness: Complementary to the above direction, the area of randomness extraction focuses on producing purely random bits from low quality sources that occur in nature. There has been remarkable recent progress in this area, and the important research goals of this project include constructing better extractors in realistic models of defective random sources and in the presence of adversaries, with applications to cryptography, and investigating the use of such extractors in unconditional de-randomization pursuits listed above.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.