Skip directly to content

Minimize RSR Award Detail

Research Spending & Results

Award Detail

Awardee:OHIO STATE UNIVERSITY, THE
Doing Business As Name:Ohio State University
PD/PI:
  • Pooya Hatami
  • (312) 282-4927
  • pooyahat@gmail.com
Award Date:01/09/2020
Estimated Total Award Amount: $ 175,000
Funds Obligated to Date: $ 175,000
  • FY 2020=$175,000
Start Date:01/15/2020
End Date:12/31/2021
Transaction Type:Grant
Agency:NSF
Awarding Agency Code:4900
Funding Agency Code:4900
CFDA Number:47.070
Primary Program Source:040100 NSF RESEARCH & RELATED ACTIVIT
Award Title or Description:CRII: AF: Pseudorandomness in Computer Science
Federal Award ID Number:1947546
DUNS ID:832127323
Parent DUNS ID:001964634
Program:Algorithmic Foundations
Program Officer:
  • A. Funda Ergun
  • (703) 292-2216
  • fergun@nsf.gov

Awardee Location

Street:Office of Sponsored Programs
City:Columbus
State:OH
ZIP:43210-1016
County:Columbus
Country:US
Awardee Cong. District:03

Primary Place of Performance

Organization Name:Ohio State University
Street:Office of Sponsored Programs
City:Columbus
State:OH
ZIP:43210-1016
County:Columbus
Country:US
Cong. District:03

Abstract at Time of Award

Randomness is a powerful tool with frequent utility in various branches of computer science such as algorithm design, cryptography, computational complexity, and distributed computing. Some of the fastest, simplest and most elegant algorithms for several fundamental problems, such as primality testing, polynomial factorization, polynomial identity testing, and graph connectivity rely heavily on randomness. This was a motivation for the formation and cultivation of the field of probabilistic computation, which emerged in 1970's as a subfield of complexity theory. After decades of research, there is an abundance of problems with efficient randomized algorithms, for which no efficient deterministic algorithms are known. A fundamental goal in theory of pseudorandomness in complexity theory is to understand the extent to which randomness is necessary for efficient computation. It is conjectured that every polynomial time randomized algorithm has a polynomial time deterministic counterpart, and every log-space randomized algorithm has a log-space deterministic counterpart. Even though the area of pseudorandomness has witnessed several breakthroughs over the recent years, these fundamental conjectures seem far out of reach, and several intermediate open problems remain to be resolved. In order to reduce or remove the use of randomness, one often faces the problem of constructing explicit or weakly explicit mathematical objects that share useful properties with purely random objects. For example, in order to derandomize all log-space randomized algorithms with only a constant factor loss in space complexity, it is sufficient to efficiently construct pseudorandom distributions (called pseudorandom generators) that use a short random string to generate a much longer ``pseudorandom'' string that looks random to log-space algorithms. Other examples of useful pseudorandom objects are hitting set generators, samplers, error correcting codes, expander graphs, and randomness extractors. Finding explicit constructions of these objects, have immediate applications that go beyond derandomization of algorithms. The goal of this project is to design efficient such pseudorandom objects that help answer fundamental questions about the role of randomness in efficient computation. 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.

For specific questions or comments about this information including the NSF Project Outcomes Report, contact us.