NP-hardness of approximating meta-complexity: a cryptographic approach

Cites work

\(\Sigma_ 1^ 1\)-formulae on finite structures
BPP has subexponential time simulations unless EXPTIME has publishable proofs
A Pseudorandom Generator from any One-way Function
A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
A threshold of ln n for approximating set cover
Analytical approach to parallel repetition
Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
Candidate indistinguishability obfuscation and functional encryption for all circuits
Candidate Multilinear Maps from Ideal Lattices
Circuit lower bounds from NP-hardness of MCSP under turing reductions
Circuit minimization problem
Computationally Sound Proofs
Cryptography from sublinear-time average-case hardness of time-bounded Kolmogorov complexity
Discrete logarithm and minimum circuit size
Fuzzy Identity-Based Encryption
Hardness of approximate two-level logic minimization and PAC learning with membership queries
Hardness of KT characterizes parallel cryptography
How to share a secret
scientific article; zbMATH DE number 5485546 (Why is no real title available?)
scientific article; zbMATH DE number 3489106 (Why is no real title available?)
scientific article; zbMATH DE number 1996402 (Why is no real title available?)
scientific article; zbMATH DE number 2081089 (Why is no real title available?)
scientific article; zbMATH DE number 7561750 (Why is no real title available?)
scientific article; zbMATH DE number 7250145 (Why is no real title available?)
scientific article; zbMATH DE number 7250147 (Why is no real title available?)
scientific article; zbMATH DE number 7650382 (Why is no real title available?)
Identity-based cryptosystems and signature schemes
Identity-Based Encryption from the Weil Pairing
Indistinguishability obfuscation from LPN over \(\mathbb{F}_p\), DLIN, and PRGs in \(NC^0\)
Indistinguishability obfuscation from simple-to-state hard problems: new assumptions, new techniques, and simplification
Limits of minimum circuit size problem as oracle
Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
Minimizing Disjunctive Normal Form Formulas and AC^0 Circuits Given a Truth Table
Minimum circuit size, graph isomorphism, and related problems
Minimum propositional proof length is NP-hard to linearly approximate
Natural proofs
New directions in cryptography
New insights on the (non-)hardness of circuit minimization and related problems
On the (im)possibility of obfuscating programs
On the (non) \(\mathsf{NP}\)-hardness of computing circuit complexity
On the average-case complexity of MCSP and its variants
On the Complexity of Learning Minimum Time-Bounded Turing Machines
On the Cryptographic Applications of Random Functions (Extended Abstract)
On the hardness of approximating label-cover
On the notion of infinite pseudorandom sequences
On the NP-Completeness of the Minimum Circuit Size Problem.
On the possibility of basing cryptography on \(\mathsf{EXP}\ne \mathsf{BPP} \)
On Worst‐Case to Average‐Case Reductions for NP Problems
One-Way Functions and (Im)perfect Obfuscation
Parity, circuits, and the polynomial-time hierarchy
Power from Random Strings
Probabilistic checking of proofs
Probabilistic encryption
Proof verification and the hardness of approximation problems
Pseudorandomness and average-case complexity via uniform reductions
Random-Self-Reducibility of Complete Sets
Reducibility among combinatorial problems
Secret-sharing for NP
Secret-Sharing Schemes: A Survey
The Complexity of Complexity
The minimum oracle circuit size problem
The non-hardness of approximating circuit size
Three approaches to the quantitative definition of information^*
Tighter connections between derandomization and circuit lower bounds
Unexpected hardness results for Kolmogorov complexity under uniform reductions
Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization
Witness encryption and its applications
Witness encryption and null-iO from evasive LWE
Zero knowledge and circuit minimization

Cited in

(7)

Gap MCSP is not (Levin) NP-complete in obfustopia
Lower bounds for Levin-Kolmogorov complexity
Symmetric exponential time requires near-maximum circuit size
A meta-complexity theoretic approach to indistinguishability obfuscation and witness pseudo-canonicalization
On the post-hoc Evaluation of PDE Discovery: A Multifaceted Challenge of Scientific Advancement
SAT reduces to the minimum circuit size problem with a random oracle
Lower bounds on the overhead of indistinguishability obfuscation

This page was built for publication: NP-hardness of approximating meta-complexity: a cryptographic approach

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6499285)