On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets

DOI10.1007/978-3-030-41672-0_6zbMath1440.68142OpenAlexW2918847199MaRDI QIDQ3297825

Osamu Watanabe, Shuichi Hirahara

Publication date: 20 July 2020

Published in: Complexity and Approximation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-41672-0_6

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Related Items (2)

Capturing one-way functions via NP-hardness of meta-complexity ⋮ Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Some consequences of non-uniform conditions on uniform classes
• On helping by robust oracle machines
• Hardness vs randomness
• Limits on the computational power of random strings
• Zero knowledge and circuit minimization
• Pseudorandomness and average-case complexity via uniform reductions
• Efficiency Improvements in Constructing Pseudorandom Generators from One-Way Functions
• Erratum for
• On basing one-way functions on NP-hardness
• Random-Self-Reducibility of Complete Sets
• Circuit minimization problem
• On the Complexity of Learning Minimum Time-Bounded Turing Machines
• Limitations of Hardness vs. Randomness under Uniform Reductions
• Key agreement from weak bit agreement
• Randomness conservation inequalities; information and independence in mathematical theories
• A Pseudorandom Generator from any One-way Function
• New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems
• On Basing Size-Verifiable One-Way Functions on NP-Hardness
• Learning algorithms from natural proofs
• Power from Random Strings
• On Worst‐Case to Average‐Case Reductions for NP Problems
• An Unconditional Study of Computational Zero Knowledge
• Theory of Cryptography
• Natural proofs

This page was built for publication: On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets