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

Cites Work

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

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