Abstract

A hitting set is a "one-sided" variant of a pseudorandom generator (PRG), naturally suited to derandomizing algorithms that have one-sided error. We study the problem of using a given hitting set to derandomize algorithms that have two-sided error, focusing on space-bounded algorithms. For our first result, we show that if there is a log-space hitting set for polynomial-width read-once branching programs (ROBPs), then not only does L = RL, but L = BPL as well. This answers a question raised by Hoza and Zuckerman [HZ18].

Next, we consider constant-width ROBPs. We show that if there are log-space hitting sets for constant-width ROBPs, then given black-box access to a constant-width ROBP, it is possible to deterministically estimate acceptance probability within epsilon bias, in space O(log(n/epsilon)). Unconditionally, we give a deterministic algorithm for this problem with space complexity O(log^2 n + log(1/epsilon)), slightly improving over previous work.

Finally, we investigate the limits of this line of work. Perhaps the strongest reduction along these lines one could hope for would say that for every explicit hitting set, there is an explicit PRG with similar parameters. In the setting of constant-width ROBPs over a large alphabet, we prove that establishing such a strong reduction is at least as difficult as constructing a good PRG outright.

Biography

Kuan Cheng joined Peking University in July 2020 and is currently an assistant professor at CFCS, PKU. Previously he was a postdoct at University of Texas at Austin. He received his PhD in computer science from Johns Hopkins University in 2019. His research interests mainly include computational models and complexity, pseudorandomness and coding. He is also interested in learning theory and networks.

Admission: https://www.wjx.cn/m/84953938.aspx
Online Talk: https://zoom.com.cn/j/94266448667