Our first TOCA-SV meeting of the academic year is coming up next Friday, in Tressider Oak Lounge, Stanford. Like last year, it will host the Motwani Colloquium. We have reserved some parking (see instructions below) on a first come first serve basis (so come early). Also see the schedule and abstract below.
There are 35 reserved spaces in Tresidder Lot (L-39) on November 15, 2019. Our space numbers will be 14-48; see map for location. Posted signs to read Reserved for TOCA-SV CS Workshop.
To avoid a citation, vehicle information is required to obtain permission to park in the designated reserved area. Use: https://stanford.nupark.com/v2/portal/eventregister/5201e8f7-9339-4acf-8416-62f137dbc523 See instructions.
*Internet browser Chrome or Firefox are recommended and most compatible with the system.
- Dean Doron, Stanford University,
Existing techniques for derandomizing algorithms based on circuit lower bounds yield a large polynomial slowdown in running time. We show that assuming exponential lower bounds against nondeterministic circuits, we can convert any randomized algorithm running in time T to a deterministic one running in time nearly T^2. Under complexity-theoretic assumptions, such a slowdown is nearly optimal.
In this talk I will concentrate on the role of error-correcting codes in those techniques. We will see which properties of error-correcting codes are useful for constructing pseudorandomness primitives sufficient for derandomization, where they came short of achieving better slowdown, and how we can overcome that.
Based on joint work with Dana Moshkovitz, Justin Oh and David Zuckerman