Google, IBM & Meta Certificates — All 10,000+ Courses at 40% Off
One annual plan covers every course and certificate on Coursera. 40% off for a limited time.
Get Full Access
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.
