BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//hacksw/handcal//NONSGML v1.0//EN
BEGIN:VEVENT
UID:node-12420@prod.cs.cornell.edu
DTSTAMP:20221107T204500Z
DTSTART:20221107T204500Z
DTEND:20221107T213500Z
SUMMARY:Almost Chor-Goldreich Sources and Adversarial Random Walks
DESCRIPTION:David Zuckerman, UT Austin. 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...https://prod.cs.cornell.edu/content/almost-chor-goldreich-sources-and-adversarial-random-walks
LOCATION:Gates 114 and streaming (via Zoom)
END:VEVENT
END:VCALENDAR