Computer Science/Discrete Mathematics Seminar II

This is the third and final talk in the joint series with Lijie Chen. The talk will NOT rely on the technical contents from the two previous talks.

I will present a joint work with Lijie, in which we revise the hardness vs randomness framework so that it can work in a non-black-box fashion. That is, we construct derandomization algorithms that do not rely on classical PRGs, and instead "extract pseudorandomness" from the given input on which we want to simulate the probabilistic machine.

Using a non-black-box approach allows us to deduce stronger conclusions (or alternatively rely on weaker hypotheses), compared to classical approaches. In particular, I will present two such results:

1. "Free lunch" derandomization, in which we eliminate randomness at essentially no observable cost in the running time.

2. A new approach to the prBPP = prP conjecture, which connects the conjecture to a specific type of uniform lower bounds that we introduce.