Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization - Lijie Chen

Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization - Lijie Chen

Institute for Advanced Study via YouTube Direct link

Subsequent Developments

4 of 14

4 of 14

Subsequent Developments

Class Central Classrooms beta

YouTube videos 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. 1 Intro
  2. 2 (Oversimplified) History and Motivation
  3. 3 (Oversimplified) History: Part 2
  4. 4 Subsequent Developments
  5. 5 Black-box and White-box Derandomization
  6. 6 Alternative Plan for Average-case?
  7. 7 Difficulties with previous approaches
  8. 8 Circuit Lower Bounds and Derandomization
  9. 9 Derandomizing Merlin-Arthur yields Average-Case Circuit Lower Bounds
  10. 10 Bootstrapping of Derandomization to NPRG
  11. 11 Partial Solution: Conditional A.E. MA
  12. 12 Adaptation to the Average-Case
  13. 13 Conditional Construction of NPRG: Adapted
  14. 14 The Key Issue on Improving C.'19 The Updated Question

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.