Skip directly to content

Minimize RSR Award Detail

Research Spending & Results

Award Detail

Doing Business As Name:Iowa State University
  • Pavan Aduri
  • (515) 294-5225
Award Date:08/31/2021
Estimated Total Award Amount: $ 228,000
Funds Obligated to Date: $ 228,000
  • FY 2021=$228,000
Start Date:10/01/2021
End Date:09/30/2024
Transaction Type:Grant
Awarding Agency Code:4900
Funding Agency Code:4900
CFDA Number:47.070
Primary Program Source:040100 NSF RESEARCH & RELATED ACTIVIT
Award Title or Description:Collaborative Research: AF: Small: Weak Derandomizations in Time and Space Complexity
Federal Award ID Number:2130536
DUNS ID:005309844
Parent DUNS ID:005309844
Program:Algorithmic Foundations
Program Officer:
  • Tracy Kimbrel
  • (703) 292-7924

Awardee Location

Street:1138 Pearson
Awardee Cong. District:04

Primary Place of Performance

Organization Name:Iowa State University
Street:112 Atanasoff Hall
Cong. District:04

Abstract at Time of Award

Certain computational tasks such as network connectivity, sorting, and testing whether a number is a prime number admit time-efficient algorithms. On the other hand, many computational tasks, such as the traveling salesperson problem, integer factoring, and several other optimization problems, are not known to admit fast algorithms. Why does such computational disparity exist among natural computational tasks? This is a foundational question that impacts many scientific areas including mathematics, engineering, economics, optimization, and communication -- areas beyond computer science. Computational complexity theory investigates the notion of efficient computation. Typically, efficiency is measured in terms of computational resources such as time, memory, and randomness. This project aims to advance the state-of-the-art in computational complexity theory by investigating the role of randomness and its interplay with time and memory. Research findings from this project will be published in peer-reviewed venues as well as in open access venues enabling broad dissemination of scientific results. Efforts will be taken to integrate research with teaching at both graduate and undergraduate levels. Even though there is strong scientific evidence that randomized computations can be efficiently derandomized, establishing unconditional and complete derandomization results is known to be well beyond the current techniques in the field. In this context, this project will investigate certain weak but unconditional derandomizations. This is achieved by exploring (a) pseudodeterministic algorithms -- randomized algorithms that output a canonical value with high probability, and their relation to some central topics in complexity theory including completeness, promise problems, and circuit complexity; and (b) probabilistic space-bounded computations with multiple access to the random tape, and their relation to derandomization of time-bounded probabilistic classes. 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.