Theory Seminar

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.

Event Website:

http://theory.cs.cmu.edu/

For More Information, Contact:

Keywords:

Seminar Series