Friday, December 3, 2021 - 3:00pm to 4:00pm
Location:In Person Group View and Virtual Presentation - ET Gates Hillman and Zoom
Speaker:LIJIE CHEN, Ph.D. Candidate https://www.mit.edu/~lijieche/
Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise
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.
In Person Watch Gathering and Zoom Participation. See announcement.