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

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

Association for Computing Machinery (ACM) via YouTube Direct link

Circuit Analysis Problems

5 of 16

5 of 16

Circuit Analysis Problems

Class Central Classrooms beta

YouTube videos curated by Class Central.

Classroom Contents

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

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

  1. 1 Intro
  2. 2 Motivation 1: Circuit Lower Bounds
  3. 3 AC circuits
  4. 4 AC [6] circuits
  5. 5 Circuit Analysis Problems
  6. 6 Algorithmic Method
  7. 7 Subsequent Developments
  8. 8 Motivation 2: Derandomization
  9. 9 Pseudorandom Generators Fooling AC [2]?
  10. 10 This Work: Strong Average-Case Circuit Lower Bounds for ACC
  11. 11 First Attempt: Hardness Amplification
  12. 12 Still, Step I...?
  13. 13 Circuit Analysis of Approximate Sum
  14. 14 Hardness Amplification via Approximate Sum
  15. 15 The Final Proof
  16. 16 New Developments

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.