Unexpected Hardness Results for Kolmogorov Complexity Under Uniform Reductions
Association for Computing Machinery (ACM) via YouTube
Overview
Syllabus
Intro
Talk Outline
Historical Motivation
Kolmogorov's Approach towards P
Hardness of Kolmogorov-Random Strings
Limits on Hardness Results for Kolmogorov-Random Strings
Conjectures on the Upper Bounds
Why plausible?
Kolmogorov-Randomness is "Harder" than Expected!
Pseudorandom Generator Construction
Security Proof of Hardness-Based PRGS
Advice Complexity of DP is Small
Deterministic Reductions and Hardness of Kolmogorov Complexity
SAT-Oracle MCSP
Other Results
Conclusions
Taught by
Association for Computing Machinery (ACM)