Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Almost Chor–Goldreich Sources and Adversarial Random Walks
event speaker icon
Dean Doron (Ben-Gurion University)
event date icon
Wednesday, 31.05.2023, 12:30
event location icon
Taub 201
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