Roei Tell, DIMACS

Abstract

Textbook hardness-to-randomness converts circuit lower bounds into PRGs. But is this black-box approach really necessary for derandomization? In this talk I'll show how to revamp the classical hardness-to-randomness framework, converting new types of *uniform lower bounds* into *non-black-box derandomization*. This yields conclusions such as promiseBPP = promiseP without PRGs, and reveals a close connection between derandomization and the new types of uniform lower bounds. Another instantiation of this new framework allows to deduce, under plausible hypotheses, that randomness can be eliminated at essentially no observable cost when solving decision problems.
Based on a joint work with Lijie Chen.

Special Note: The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar. 

See: https://theory.cs.rutgers.edu/theory_seminar