The complexity of constructing pseudorandom generators from hard functions
From MaRDI portal
Publication:1766819
DOI10.1007/s00037-004-0187-1zbMath1061.68077OpenAlexW2058859323MaRDI QIDQ1766819
Publication date: 1 March 2005
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-004-0187-1
Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Pseudo-random numbers; Monte Carlo methods (11K45)
Related Items (16)
Incompressible functions, relative-error extractors, and the power of nondeterministic reductions ⋮ Unnamed Item ⋮ Quantified Derandomization: How to Find Water in the Ocean ⋮ Improved hardness amplification in NP ⋮ Uniform derandomization from pathetic lower bounds ⋮ Hardness amplification within NP against deterministic algorithms ⋮ Towards a tight hardness-randomness connection between permanent and arithmetic circuit identity testing ⋮ Pseudorandom generators, typically-correct derandomization, and circuit lower bounds ⋮ Unnamed Item ⋮ On derandomizing Yao's weak-to-strong OWF construction ⋮ Randomness buys depth for approximate counting ⋮ On uniformity and circuit lower bounds ⋮ Bounded-depth circuits cannot sample good codes ⋮ Unnamed Item ⋮ Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification ⋮ Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification
This page was built for publication: The complexity of constructing pseudorandom generators from hard functions
