Almost Chor-Goldreich Sources and Adversarial Random Walks (via Zoom)

Abstract: A Chor-Goldreich (CG) source is a sequence of random variables where each has min-entropy, even conditioned on the previous ones.  We extend this notion in several ways, most notably allowing each random variable to have Shannon entropy conditioned on previous ones.  We achieve pseudorandomness results for Shannon-CG sources that were not known to hold even for standard CG sources, and even for the weaker model of Santha-Vazirani sources.

Specifically, we construct a deterministic condenser that on input a Shannon-CG source, outputs a distribution that is close to having constant entropy gap, namely its min-entropy is only an additive constant less than its length.  Therefore, 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.  Moreover, our construction works in an online manner, since it is based on random walks on expanders.
Our main technical contribution is a novel analysis of random walks, which should be of independent interest. We analyze walks with adversarially correlated steps, each step being entropy-deficient, on good enough lossless expanders. We prove that such walks (or certain interleaved walks on two expanders) accumulate entropy.
Joint work with Dean Doron, Dana Moshkovitz, and Justin Oh (via Zoom)

Bio: David Zuckerman holds an Endowed Professorship in the Computer Science Department at the University of Texas at Austin. He received an A.B. in Mathematics from Harvard University, where he was a Putnam Fellow, in 1987, and a Ph.D. in Computer Science from U.C. Berkeley in 1991. He was a postdoctoral fellow at MIT from 1991-1993 and at Hebrew University in the Fall of 1993. He has been with the University of Texas since then, visiting U.C. Berkeley from 1999-2000, Harvard University from 2004-2005, and the Institute for Advanced Study from 2011-12. In Spring 2017, he visited U.C. Berkeley, co-organizing the Simons Program on Pseudorandomness.
His research focuses primarily on pseudorandomness and the role of randomness in computing. He is best known for his work on randomness extractors and their applications. His other research interests include coding theory, distributed computing, cryptography, inapproximability, and other areas of complexity theory. His research awards include a 30-Year Test of Time Award at FOCS 2021, a Simons Investigator Award, a Best Paper Award at STOC 2016, ACM Fellow, a Guggenheim Fellowship, a Packard Fellowship for Science and Engineering, a Sloan Research Fellowship, and an NSF Young Investigator Award.