Caltech Home > PMA Home > Master Calendar > CMI Seminar: Dean Doron - *3pm start time*
open search form
Tuesday, November 05, 2019
3:00 PM - 4:00 PM
Annenberg 314

CMI Seminar: Dean Doron - *3pm start time*

Nearly Optimal Pseudorandomness From Hardness
Dean Doron, Postdoctoral Fellow, Computer Science Theory Group, Stanford,

Existing proofs that deduce P=BPP from circuit lower bounds convert randomized algorithms to deterministic ones with a large polynomial slowdown in running time. In this talk, I will show that if we assume exponential lower bounds against nondeterministic circuits, we can convert any randomized algorithm running in time T to a deterministic one running in time T^{2+α} for an arbitrarily small constant α. Under complexity-theoretic assumptions, such a slowdown is nearly optimal.

Our result follows from a new pseudorandom generator whose construction uses, among other ideas, a new connection between pseudoentropy generators and locally list-recoverable codes.

Joint work with Dana Moshkovitz, Justin Oh and David Zuckerman

For more information, please contact Linda Taddeo by phone at 626-395-6704 or by email at ltaddeo@caltech.edu or visit Mathematics of Information Seminar - Upcoming Events.