Capturing One-Way Functions via NP-Hardness of Meta-Complexity
Offered By: Simons Institute via YouTube
Course Description
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
Related Courses
The Next Generation of InfrastructureDelft University of Technology via edX The Beauty and Joy of Computing - AP® CS Principles Part 2
University of California, Berkeley via edX Advanced Data Structures in Java
University of California, San Diego via Coursera Theory of Computation
Indian Institute of Technology Kanpur via Swayam 离散数学
Shanghai Jiao Tong University via Coursera