Capturing one-way functions via NP-hardness of meta-complexity
From MaRDI portal
(Redirected from Publication:6499280)
Cites work
- 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
- 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?)
- 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 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 average-case complexity of MCSP and its variants
- On the Complexity of Learning Minimum Time-Bounded Turing Machines
- On the Cryptographic Applications of Random Functions (Extended Abstract)
- On Worst‐Case to Average‐Case Reductions for NP Problems
- 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
Cited in
(7)- Quantum cryptography and meta-complexity
- Impagliazzo's worlds through the Lens of conditional Kolmogorov complexity
- A meta-complexity characterization of quantum cryptography
- Consequences of randomized reductions from SAT to time-bounded Kolmogorov complexity
- NP-hardness of approximating meta-complexity: a cryptographic approach
- Lower bounds for Levin-Kolmogorov complexity
- SAT reduces to the minimum circuit size problem with a random oracle
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)
