Unexpected Hardness Results for Kolmogorov Complexity Under Uniform Reductions

Explore the unexpected hardness results for Kolmogorov complexity under uniform reductions in this 22-minute conference talk. Delve into Kolmogorov's approach towards P, the hardness of Kolmogorov-random strings, and the limits on hardness results. Examine conjectures on upper bounds and discover why Kolmogorov-randomness is "harder" than expected. Learn about pseudorandom generator construction, security proofs of hardness-based PRGs, and the advice complexity of DP. Investigate deterministic reductions, the hardness of Kolmogorov complexity, and SAT-oracle MCSP. Gain insights into other related results and draw conclusions from this comprehensive exploration of Kolmogorov complexity and its implications in computational theory.

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