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