Seminar Details
Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise
- Start Date: September 29, 2021
- Event Start Time: 11:00 AM
- Event End Time: 12:00 PM
- Seminar Series: Theoretical Computer Science Seminar
- Presenter(s): Roei Tell - DIMACS
- Event Location: Online Event
- Event Additional Info: <p>Special Note: The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar. </p> <p>See: <a href="https://theory.cs.rutgers.edu/theory_seminar">https://theory.cs.rutgers.edu/theory_seminar</a></p>
- Presentation Type: Stand Alone Presentation
- 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.