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

Hanlin Ren (University of Oxford) https://simons.berkeley.edu/talks/hanlin-ren-university-oxford-2023-05-02 Minimal Complexity Assumptions for Cryptography It is a long-standing open problem whether the Minimum Circuit Size Problem (MCSP) and related meta-complexity problems are NP-complete. Even for the rare cases where the NP-hardness of meta-complexity problems are known, we only know very weak hardness of approximation. In this work, we prove NP-hardness of approximating meta-complexity with nearly-optimal approximation gaps. Our key idea is to use *cryptographic constructions* in our reductions, where the security of the cryptographic construction implies the correctness of the reduction. This talk will focus on a near-optimal NP-hardness of approximation result for the Minimum Oracle Circuit Size Problem (MOCSP), where Yes instances have circuit complexity at most 2^{eps n}, and No instances are essentially as hard as random truth tables. Our reduction builds on a witness encryption construction proposed by Garg, Gentry, Sahai, and Waters (STOC'13). Previously, it was unknown whether it is NP-hard to distinguish between oracle circuit complexity s versus 10*s*log N.