EAGER: AF: Collaborative Research: Weak Derandomizations in Time and Space Complexity

Iowa State University, Ames IA

Investigators

Abstract

Computational complexity theory classifies natural computational problems into various complexity classes based on the amount of resources needed to solve them. Typical resources are time, memory, amount of randomness, and circuit size. This project aims to advance the state of the art in understanding the power and limitations of randomness and circuit size, using two new, previously untested, techniques. Intuition gained from this project will enhance our understanding of practical computational problems arising from fields beyond computer science. The project's exploration has the potential to solve central, longstanding, open questions in complexity theory. The first part of the project will investigate unconditional de-randomization of probabilistic time via de-randomization of multi-pass, probabilistic space-bounded computations. In particular, this project will explore a new approach to obtain an asymptotically better deterministic simulation of probabilistic linear time than what is currently known. The second part of this project aims to prove new fixed-polynomial size circuit lower bounds via designing pseudo-deterministic approximation algorithms for certain counting problems. 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.