New Directions in Derandomization: Non-Black-Box Techniques, Superfast Algorithms
, Institute for Advanced Study
Date: Tuesday, April 12, 2022
Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone
Location: 32-G449 (Kiva)
Event Type: Seminar
Room Description: 32-G449 (Kiva)
Host: Ryan Williams, MIT CSAIL
Contact: Nathan Higgins, firstname.lastname@example.org
Speaker URL: None
TALK: New Directions in Derandomization: Non-Black-Box Techniques, Superfast Algorithms
This talk will present two new directions in the study of derandomization, which are related to each other. The talk is based on a sequence of recent works with Lijie Chen (some of the works are upcoming).
The first direction is avoiding classical PRGs in favor of *non-black-box techniques*, which extract pseudorandomness for a probabilistic machine from the code of that specific machine. This approach allows us to construct derandomization algorithms from weaker hypotheses (compared to classical results), or alternatively to construct very fast derandomization algorithms that cannot be obtained using classical PRGs. The second direction is the fine-grained study of *superfast derandomization*, asking what is the smallest possible overhead that we need to pay when eliminating randomness (and if we can get away with paying nothing at all).
As examples, we will mention four results:
1. Connecting the BPP = P conjecture to a new type of lower bounds.
2. "Free lunch" derandomization with essentially no time overhead.
3. Superfast derandomization of probabilistic proof systems.
4. Average-case derandomization from weak hardness assumptions. (Joint work with Ron Rothblum.)
Algorithms & Theory
Created by Nathan Higgins at Friday, March 25, 2022 at 11:09 AM.