New Directions in Derandomization: Non-Black-Box Techniques, Superfast Algorithms

Speaker: Roei Tell , 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

Public: Yes

Location: 32-G449 (Kiva)

Event Type: Seminar

Room Description: 32-G449 (Kiva)

Host: Ryan Williams, MIT CSAIL

Contact: Nathan Higgins, nhiggins@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: theory-seminars@lists.csail.mit.edu, seminars@lists.csail.mit.edu

Reminder Subject: 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.)

Research Areas:
Algorithms & Theory

Impact Areas:

See other events that are part of the Theory of Computation (ToC) Seminar 2022.

Created by Nathan Higgins at Friday, March 25, 2022 at 11:09 AM.