Derandomization from Algebraic Hardness - Treading the Borders

Derandomization from Algebraic Hardness - Treading the Borders

IEEE FOCS: Foundations of Computer Science via YouTube Direct link

Some consequences

8 of 18

8 of 18

Some consequences

Class Central Classrooms beta

YouTube videos curated by Class Central.

Classroom Contents

Derandomization from Algebraic Hardness - Treading the Borders

Automatically move to the next video in the Classroom when playback concludes

  1. 1 Intro
  2. 2 Algebraic Circuits
  3. 3 Two Important Questions
  4. 4 Lower bounds and hitting sets
  5. 5 How are hitting sets constructed?
  6. 6 Generators from hardness
  7. 7 Main Theorem
  8. 8 Some consequences
  9. 9 Consequences for bootstrapping
  10. 10 The one trick that we use
  11. 11 Description of our generator
  12. 12 Proof overview
  13. 13 The univariate setting
  14. 14 Reconstruction of P
  15. 15 Reconstruction Step: Pictorially
  16. 16 No more fuss about the border
  17. 17 Improvements to bootstrapping
  18. 18 Conclusion

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.