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

on YouTube ↗45m

" summary

Shows NP‑hardness gaps for concrete meta‑complexity problems: under subexponentially‑secure indistinguishability obfuscation/witness encryption the conditional time‑bounded Kolmogorov complexity Kt(x|y) is NP‑hard to approximate up to essentially optimal (nearly maximal vs polynomially small) gaps in the superlinear time regime; using SNARGs and multilinear‑map style constructions the reductions are syntactic and black‑box; unconditionally proves MOCSP is NP‑hard to approximate with Yes instances of size s and No instances ≥ s^c.

AI-written summary · about

" chapters (13)

1. 0:00Introduction
2. 0:30Joint work
3. 0:55Eric Allender
4. 1:35First email from Eric
5. 3:09Working with Eric
6. 7:43NPHardness and Cryptography
7. 14:31Cryptographic Objects
8. 16:55Conditional MetaComplexity
9. 27:57Witness Encryption
10. 33:17Proof
11. 34:37Encryption
12. 37:07Unconditional
13. 39:37Secret Sharing

" related talks

• 46mNP-Hardness of Approximating Meta-Complexity: A Cryptographic ApproachHanlin Ren · Minimal Complexity Assumptions for Cryptography 2023
• 01h 06mCrypto + Meta-complexity 1Rafael Pass · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 48mTales of Obfuscation in Bounded Arithmetic, Metacomplexity, and Differential PrivacyRahul Ilango · Minimal Complexity Assumptions for Cryptography 2023
• 01h 05mCryptography and Kolmogorov Complexity: A Quick TutorialYanyi Liu · Minimal Complexity Assumptions for Cryptography 2023
• 59mBeyond P versus NP: Using Complexity Theory in Obfuscation and Vice-VersaAlex Lombardi, Rahul Ilango · Obfuscation
• 47mCapturing One-Way Functions via NP-Hardness of Meta-ComplexityShuichi Hirahara · Minimal Complexity Assumptions for Cryptography 2023
• 01h 17mCrypto + Meta-complexity 2Rafael Pass · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 49mLower Bounds on the Overhead of Indistinguishability ObfuscationNoam Mazor · Obfuscation