TCS+ Talk
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>=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.
There are three ways to watch the talk:
- Watching the live stream. At the announced start time of the talk (or a minute before), a live video stream will be available on our "next talk" page. Simply connect to the page and enjoy the talk. No webcam or registration is needed. Questions and comments during the talk are welcome (text only, unfortunately); simply post a comment below the live video stream on YouTube.
- Joining the live hangout. Those we wish to be part of the hangout (and hence be visible, and be able to ask questions through the teleconference), need a reasonably modern computer with a webcam. There is a limit on the number of participants who can join this way. We therefore ask parties to bid on the "seat reservation" page as early as possible. More detailed instructions for those joining the hangouts appear below.
- Watching the recorded talk offline. The recorded talk will be made available shortly after the talk ends on our YouTube page. (Please leave a comment if you enjoyed it!)