Unexpected Hardness Results for Kolmogorov Complexity Under Uniform Reductions

Unexpected Hardness Results for Kolmogorov Complexity Under Uniform Reductions

Association for Computing Machinery (ACM) via YouTube Direct link

Other Results

15 of 16

15 of 16

Other Results

Class Central Classrooms beta

YouTube videos 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. 1 Intro
  2. 2 Talk Outline
  3. 3 Historical Motivation
  4. 4 Kolmogorov's Approach towards P
  5. 5 Hardness of Kolmogorov-Random Strings
  6. 6 Limits on Hardness Results for Kolmogorov-Random Strings
  7. 7 Conjectures on the Upper Bounds
  8. 8 Why plausible?
  9. 9 Kolmogorov-Randomness is "Harder" than Expected!
  10. 10 Pseudorandom Generator Construction
  11. 11 Security Proof of Hardness-Based PRGS
  12. 12 Advice Complexity of DP is Small
  13. 13 Deterministic Reductions and Hardness of Kolmogorov Complexity
  14. 14 SAT-Oracle MCSP
  15. 15 Other Results
  16. 16 Conclusions

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.