Theory Lunch Seminar - Jiatu Li

— 1:00pm

Location:
In Person - Reddy Conference Room, Gates Hillman 4405

Speaker:
JIATU LI, Ph.D. Student, Theory Group, Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology
http://ljt12138.github.io/

This work revisits the study of two classical technical tools in theoretical computer science: Yao's transformation of distinguishers to next-bit predictors (FOCS 1982), and the "reconstruction paradigm" in pseudorandomness (e.g., as in Nisan and Wigderson, JCSS 1994). Recent works of Pyne, Raz, and Zhan (FOCS 2023) and Doron, Pyne, and Tell (STOC 2024) showed that both of these tools can be derandomized in the specific context of read-once branching programs (ROBPs), but left open the question of derandomizing them in more general settings.

Our main contributions give appealing evidence that derandomization of the two tools is possible in general settings, show surprisingly strong consequences of such derandomization, and reveal several new settings where such derandomization is unconditionally possible for algorithms stronger than ROBPs (with useful consequences). In particular, we prove that deterministically solving the search problem of producing a transformation from distinguishers to next-bit predictors (i.e. derandomizing Yao's lemma) if equivalent to generic derandomization prBPP = prP. 

This is a joint work with Edward Pyne (MIT) and Roei Tell (University of Toronto) to appear in FOCS 2024. 

→  Full version of the paper.

Event Website:
https://www.cs.cmu.edu/~theorylunch/abstractsHTML/20241002.html

Add event to Google
Add event to iCal