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

Cites work

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?)
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 Multilinear Maps from Ideal Lattices
Candidate indistinguishability obfuscation and functional encryption for all circuits
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 KT characterizes parallel cryptography
Hardness of approximate two-level logic minimization and PAC learning with membership queries
How to share a secret
Identity-Based Encryption from the Weil Pairing
Identity-based cryptosystems and signature schemes
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 Worst‐Case to Average‐Case Reductions for NP Problems
On the (im)possibility of obfuscating programs
On the (non) $\mathsf{NP}$-hardness of computing circuit complexity
On the Complexity of Learning Minimum Time-Bounded Turing Machines
On the Cryptographic Applications of Random Functions (Extended Abstract)
On the NP-Completeness of the Minimum Circuit Size Problem.
On the average-case complexity of MCSP and its variants
On the hardness of approximating label-cover
On the notion of infinite pseudorandom sequences
On the possibility of basing cryptography on $\mathsf{EXP}\ne \mathsf{BPP} $
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 Schemes: A Survey
Secret-sharing for NP
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
$BPP$ has subexponential time simulations unless $EXPTIME$ has publishable proofs
$\Sigma_ 1^ 1$-formulae on finite structures

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)