Completed
Historical Motivation
Class Central Classrooms beta
YouTube playlists curated by Class Central.
Classroom Contents
Unexpected Hardness Results for Kolmogorov Complexity Under Uniform Reductions
Automatically move to the next video in the Classroom when playback concludes
- 1 Intro
- 2 Talk Outline
- 3 Historical Motivation
- 4 Kolmogorov's Approach towards P
- 5 Hardness of Kolmogorov-Random Strings
- 6 Limits on Hardness Results for Kolmogorov-Random Strings
- 7 Conjectures on the Upper Bounds
- 8 Why plausible?
- 9 Kolmogorov-Randomness is "Harder" than Expected!
- 10 Pseudorandom Generator Construction
- 11 Security Proof of Hardness-Based PRGS
- 12 Advice Complexity of DP is Small
- 13 Deterministic Reductions and Hardness of Kolmogorov Complexity
- 14 SAT-Oracle MCSP
- 15 Other Results
- 16 Conclusions
