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

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Bit commitment using pseudorandomness
Randomness vs time: Derandomization under a uniform assumption
Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
Super-logarithmic depth lower bounds via the direct sum in communication complexity
Computational depth: Concept and applications
Pseudorandomness and average-case complexity via uniform reductions
If NP languages are hard on the worst-case, then it is easy to find their hard instances
On basing one-way functions on NP-hardness
On the Cryptographic Applications of Random Functions (Extended Abstract)
Random-Self-Reducibility of Complete Sets
Circuit minimization problem
On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets
On the Complexity of Learning Minimum Time-Bounded Turing Machines
Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization
Limitations of Hardness vs. Randomness under Uniform Reductions
Worst-Case to Average-Case Reductions Revisited
Average Case Complete Problems
A Pseudorandom Generator from any One-way Function
Foundations of Cryptography
Designing programs that check their work
The Shrinkage Exponent of de Morgan Formulas is 2
Circuit lower bounds from NP-hardness of MCSP under turing reductions
On Basing Size-Verifiable One-Way Functions on NP-Hardness
On Worst‐Case to Average‐Case Reductions for NP Problems
An Unconditional Study of Computational Zero Knowledge
Cryptography from Information Loss.
Theory of Cryptography
Conditional complexity and codes
Average-case hardness of NP from exponential worst-case hardness assumptions

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