From Distinguishers To Predictors and Beyond
Host
Rahul Ilango
MIT
Abstract:
A central tool for constructing pseudorandom generators has been the “reconstruction paradigm” — proofs that if a generator fails to fool a circuit C, we can compute a supposedly-hard function f more efficiently with the help of C. Going from C to a small circuit for f crucially uses Yao's transformation of distinguishers to next-bit predictors. In fact, this transformation is the “bottleneck” in many results in pseudorandomness.
A recent line of work has investigated the complexity of this transformation — how hard is it to turn distinguishers into predictors? Can we do it more efficiently? And what can we get out of it? I'll describe recent work that partially answers these questions, and obtains new win-win results in space complexity.
Based on joint works with Dean Doron, Jiatu Li, Roei Tell, and Ryan Williams.
A central tool for constructing pseudorandom generators has been the “reconstruction paradigm” — proofs that if a generator fails to fool a circuit C, we can compute a supposedly-hard function f more efficiently with the help of C. Going from C to a small circuit for f crucially uses Yao's transformation of distinguishers to next-bit predictors. In fact, this transformation is the “bottleneck” in many results in pseudorandomness.
A recent line of work has investigated the complexity of this transformation — how hard is it to turn distinguishers into predictors? Can we do it more efficiently? And what can we get out of it? I'll describe recent work that partially answers these questions, and obtains new win-win results in space complexity.
Based on joint works with Dean Doron, Jiatu Li, Roei Tell, and Ryan Williams.