Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

Unexpected Hardness Results for Kolmogorov Complexity Under Uniform Reductions

Association for Computing Machinery (ACM) via YouTube

Overview

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.

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)

Reviews

Start your review of Unexpected Hardness Results for Kolmogorov Complexity Under Uniform Reductions

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.