Completed
Alternative Plan for Average-case?
Class Central Classrooms beta
YouTube playlists curated by Class Central.
Classroom Contents
Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization - Lijie Chen
Automatically move to the next video in the Classroom when playback concludes
- 1 Intro
- 2 (Oversimplified) History and Motivation
- 3 (Oversimplified) History: Part 2
- 4 Subsequent Developments
- 5 Black-box and White-box Derandomization
- 6 Alternative Plan for Average-case?
- 7 Difficulties with previous approaches
- 8 Circuit Lower Bounds and Derandomization
- 9 Derandomizing Merlin-Arthur yields Average-Case Circuit Lower Bounds
- 10 Bootstrapping of Derandomization to NPRG
- 11 Partial Solution: Conditional A.E. MA
- 12 Adaptation to the Average-Case
- 13 Conditional Construction of NPRG: Adapted
- 14 The Key Issue on Improving C.'19 The Updated Question
