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 (1)

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