TCS+ talk: Wednesday, March 25 — Dana Moshkovitz, UT Austin

by plustcs

The next TCS+ talk will take place this coming Wednesday, March 25th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 18:00 Central European Time, 17:00 UTC). Dana Moshkovitz from UT Austin will speak about “Nearly Optimal Pseudorandomness From Hardness” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. (The link will also be posted on our website on the day of the talk, so people who did not sign up will still be able to join, until the maximum capacity of 300 seats is reached.) As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: Existing proofs that deduce BPP=P from circuit lower bounds convert randomized algorithms into deterministic algorithms with a large polynomial slowdown. We convert randomized algorithms into deterministic ones with little slowdown. Specifically, assuming exponential lower bounds against randomized single-valued nondeterministic (SVN) circuits, we convert any randomized algorithm over inputs of length n running in time t\geq n to a deterministic one running in time t^{2+\alpha} for an arbitrarily small constant \alpha > 0. Such a slowdown is nearly optimal, as, under complexity-theoretic assumptions, there are problems with an inherent quadratic derandomization slowdown. We also convert any randomized algorithm that errs rarely into a deterministic algorithm having a similar running time (with pre-processing). The latter derandomization result holds under weaker assumptions, of exponential lower bounds against deterministic SVN circuits. Our results follow from a new, nearly optimal, explicit pseudorandom generator. The construction uses, among other ideas, a new connection between pseudoentropy generators and locally list recoverable codes.