Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization - Lijie Chen
Institute for Advanced Study via YouTube
Overview
Syllabus
Intro
(Oversimplified) History and Motivation
(Oversimplified) History: Part 2
Subsequent Developments
Black-box and White-box Derandomization
Alternative Plan for Average-case?
Difficulties with previous approaches
Circuit Lower Bounds and Derandomization
Derandomizing Merlin-Arthur yields Average-Case Circuit Lower Bounds
Bootstrapping of Derandomization to NPRG
Partial Solution: Conditional A.E. MA
Adaptation to the Average-Case
Conditional Construction of NPRG: Adapted
The Key Issue on Improving C.'19 The Updated Question
Taught by
Institute for Advanced Study