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

on YouTube ↗46m

" summary

Proves NP-hardness of approximating Minimum Oracle Circuit Size Problem with a near‑optimal gap: Yes instances admit O‑oracle circuits of size ≤ 2^{ε n}, No instances are average‑case hard like random truth tables (requires ~2^{Ω(ε n)} size to correlate). Reduction embeds encryptions of each truth‑table bit using the Garg–Gentry–Sahai–Waters witness encryption, implemented in a carefully sampled multilinear map oracle so witness encryption security implies correctness of the reduction.

AI-written summary · about

" chapters (7)

1. 0:00Start
2. 3:30Minimum Circuit Size Problem
3. 8:37Minimum Oracle Circuit Size Problem
4. 10:43Hardness of Approximation...?
5. 16:53Warm-Up: Arguments
6. 20:09Oracle Witness Encryption
7. 44:06Summary

" related talks

• 45mNP-Hardness of Approximating Meta-Complexity: A Cryptographic ApproachRahul Ilango · Lower Bounds, Learning, and Average-Case Complexity
• 01h 01mLocal Proofs Approaching the Witness LengthRon D. Rothblum · Proofs, Consensus, and Decentralizing Society Reunion 2020
• 01h 17mCrypto + Meta-complexity 2Rafael Pass · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 01h 06mCrypto + Meta-complexity 1Rafael Pass · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 49mLower Bounds on the Overhead of Indistinguishability ObfuscationNoam Mazor · Obfuscation
• 46mCryptography from Sublinear-Time Average-Case Hardness of Time-Bounded Kolmogorov ComplexityYanyi Liu · Lower Bounds, Learning, and Average-Case Complexity
• 59mBeyond P versus NP: Using Complexity Theory in Obfuscation and Vice-VersaAlex Lombardi, Rahul Ilango · Obfuscation
• 49mSubquadratic SNARGs in the Random Oracle ModelEylon Yogev · Proofs, Consensus, and Decentralizing Society Reunion 2020