Capturing one-way functions via NP-hardness of meta-complexity

Cites work

scientific article; zbMATH DE number 4179276 (Why is no real title available?)
scientific article; zbMATH DE number 5081744 (Why is no real title available?)
scientific article; zbMATH DE number 7515768 (Why is no real title available?)
scientific article; zbMATH DE number 7561748 (Why is no real title available?)
scientific article; zbMATH DE number 7650416 (Why is no real title available?)
A Pseudorandom Generator from any One-way Function
An Unconditional Study of Computational Zero Knowledge
Average Case Complete Problems
Average-case hardness of NP from exponential worst-case hardness assumptions
Bit commitment using pseudorandomness
Circuit lower bounds from NP-hardness of MCSP under turing reductions
Circuit minimization problem
Computational depth: Concept and applications
Conditional complexity and codes
Cryptography from Information Loss.
Designing programs that check their work
Foundations of Cryptography
If NP languages are hard on the worst-case, then it is easy to find their hard instances
Limitations of Hardness vs. Randomness under Uniform Reductions
On Worst‐Case to Average‐Case Reductions for NP Problems
On basing one-way functions on NP-hardness
On basing size-verifiable one-way functions on NP-hardness
On nonadaptive reductions to the set of random strings and its dense subsets
On the Complexity of Learning Minimum Time-Bounded Turing Machines
On the Cryptographic Applications of Random Functions (Extended Abstract)
On the average-case complexity of MCSP and its variants
Pseudorandomness and average-case complexity via uniform reductions
Random-Self-Reducibility of Complete Sets
Randomness vs time: Derandomization under a uniform assumption
Super-logarithmic depth lower bounds via the direct sum in communication complexity
The Shrinkage Exponent of de Morgan Formulas is 2
Theory of Cryptography
Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization
Worst-Case to Average-Case Reductions Revisited

This page was built for publication: Capturing one-way functions via NP-hardness of meta-complexity

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