The Taub Faculty of Computer Science Events and Talks

In this talk we consider the following adversarial, non-Markovian, random walk on “good enough” expanders: Starting from some fixed vertex, walk according to the instructions X = X1,…,Xt, where each Xi is only somewhat close to having only little entropy, conditioned on any prefix. The Xi-s are not independent, meaning that the distribution of the next step depends not only on the walk’s current node, but also on the path it took to get there. We show that such walks (or certain variants of them) accumulate most of the entropy in X. We call such X-s “almost Chor–Goldreich (CG) Sources”, and our result gives deterministic condensers with constant entropy gap for such sources, which were not known to exist even for standard CG sources, and even for the weaker model of Santha–Vazirani sources. As a consequence, we can simulate any randomized algorithm with small failure probability using almost CG sources with no multiplicative slowdown. This result extends to randomized protocols as well, and any setting in which we cannot simply cycle over all seeds, and a “one-shot” simulation is needed. Joint work with Dana Moshkovitz, Justin Oh, and David Zuckerman