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

YouTube

Capturing One-Way Functions via NP-Hardness of Meta-Complexity

Simons Institute via YouTube

Overview

Explore a groundbreaking lecture on the characterization of one-way functions through worst-case hardness assumptions. Delve into the relationship between one-way functions, NP-hardness, and distributional Kolmogorov complexity. Examine how this characterization suggests that recent meta-complexity approaches to exclude Heuristica and Pessiland from Impagliazzo's five worlds are both sufficient and necessary. Gain insights into the implications of this research for minimal complexity assumptions in cryptography, presented by Shuichi Hirahara from the National Institute of Informatics in Tokyo.

Syllabus

Capturing One-Way Functions via NP-Hardness of Meta-Complexity

Taught by

Simons Institute

Reviews

Start your review of Capturing One-Way Functions via NP-Hardness of Meta-Complexity

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.