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

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.

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