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 worst-case derandomization and the new types of uniform lower bounds. Another instantiation of this new framework allows us 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 Roei Tell.

Time

2021-12-23  10:00 - 11:00   

Speaker

Lijie Chen, Massachusetts Institute of Techonology

Room

Tencent meeting ID: 209454302; PW: 873355