Almost Chor-Goldreich Sources and Adversarial Random Walks
Tuesday, October 25, 2022 - 4:15pm to 5:15pm
Refreshments:
Milk & Cookies served 4--4:15 pm
Location:
32-G449 (Patil/Kiva)
Speaker:
David Zuckerman (The University of Texas at Austin)
Seminar group:
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. This readily implies fast simulation results:
1. We can simulate BPP using Shannon-CG sources with constant multiplicative slowdown. This can also be inferred from previous work, but wasn't explicitly stated before.
2. When the randomized algorithm has small failure probability, we can simulate it using Shannon-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.
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. Thus, our condenser processes the source in an online manner.
Joint work with Dean Doron, Dana Moshkovitz, and Justin Oh.
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. This readily implies fast simulation results:
1. We can simulate BPP using Shannon-CG sources with constant multiplicative slowdown. This can also be inferred from previous work, but wasn't explicitly stated before.
2. When the randomized algorithm has small failure probability, we can simulate it using Shannon-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.
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. Thus, our condenser processes the source in an online manner.
Joint work with Dean Doron, Dana Moshkovitz, and Justin Oh.
--------
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, with sabbaticals at U.C. Berkeley, Harvard University, and the Institute for Advanced Study.
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.