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

Cites Work

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

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)