Lunch In Theory This Thursday (12:00 PM, 01/22, GCS 302c)

[Devansh Gupta]

Hi all,

Please join us for Lunch in Theory this Thursday, 01/22 at 12:00 PM in GCS 302c. This week we have Kuan Cheng presenting a talk on Pseudorandom Generators for ROBP. Please find the title and abstract attached.

Reminder: Please bring your own lunch, as lunch will not be provided.

Best,

Devansh

Title: Weighted Pseudorandom Generators for Read-Once Branching Programs via Weighted Pseudorandom Reductions

Abstract: I will first describe a recent research line on derandomizing Logspace Randomized Computations, especially about weighted pseudorandom generators (WPRGs),  derandmizing algorithms, and their variants in different settings. Then I will introduce our recent results on this line, including improved WPRGs for standard read-once branching programs (ROBPs) and permutation ROBPs, and new derandmizations for regular ROBPs. The talk is based on a joint work with Ruiyang Wu on SODA26.

Bio: Kuan Cheng is an assistant professor at School of Computer Science,  Peking University. Previously he was a postdoc at UT Austin. He received his PhD from Johns Hopkins University in 2019. His research interests mainly include Pseudorandomness, Complexity and Coding theory. He is also interested in Machine Learning and Quantum Computing.