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:

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.

--------

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.