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

YouTube

NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach

Simons Institute via YouTube

Overview

Save Big on Coursera Plus. 7,000+ courses at $160 off. Limited Time Only!
Explore a 46-minute lecture on the NP-hardness of approximating meta-complexity using a cryptographic approach. Delve into Hanlin Ren's presentation from the University of Oxford, part of the Simons Institute's series on Minimal Complexity Assumptions for Cryptography. Discover how cryptographic constructions are utilized in reductions to prove NP-hardness of approximating meta-complexity with nearly-optimal approximation gaps. Examine the near-optimal NP-hardness of approximation result for the Minimum Oracle Circuit Size Problem (MOCSP), where the reduction builds on a witness encryption construction. Learn about the significant advancement from previous knowledge, where distinguishing between oracle circuit complexity s versus 10*s*log N was not known to be NP-hard.

Syllabus

NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach

Taught by

Simons Institute

Reviews

Start your review of NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach

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.