On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets
From MaRDI portal
Publication:3297825
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
Analysis of algorithms and problem complexity (68Q25) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)
Related Items (1)
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
