The complexity of constructing pseudorandom generators from hard functions

DOI10.1007/S00037-004-0187-1zbMath1061.68077OpenAlexW2058859323MaRDI QIDQ1766819

Emanuele Viola

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

zbMATH Keywords

noise sensitivityhardnessconstant-depth circuitPseudorandom generator

Mathematics Subject Classification ID

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