The complexity of constructing pseudorandom generators from hard functions

DOI10.1007/S00037-004-0187-1MaRDI QIDQ1766819zbMATH OpenOpenAlexFDO

Authors 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

hardnessnoise sensitivityconstant-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)

Recommendations

• On linear-size pseudorandom generators and hardcore functions
• On linear-size pseudorandom generators and hardcore functions
• Theory of Cryptography
• On the Complexity of Hardness Amplification
• Theory of Cryptography

Cited in

(36)

• On the hardness against constant-depth linear-size circuits
• Lower bounds on black-box reductions of hitting to density estimation
• Bounded-depth circuits cannot sample good codes
• Efficient Pseudorandom Generators from Exponentially Hard One-Way Functions
• Constructive separations and their consequences
• Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification
• ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD NP ∩ coNP FUNCTION
• Pseudo-random generators for all hardnesses
• Computational Randomness from Generalized Hardcore Sets
• Theory of Cryptography
• scientific article; zbMATH DE number 7754310 (Why is no real title available?)
• Pseudorandom generators, typically-correct derandomization, and circuit lower bounds
• scientific article; zbMATH DE number 7561748 (Why is no real title available?)
• Incompressible functions, relative-error extractors, and the power of nondeterministic reductions
• Improved hardness amplification in NP
• On the Complexity of Non-adaptively Increasing the Stretch of Pseudorandom Generators
• Theory of Cryptography
• Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification
• On linear-size pseudorandom generators and hardcore functions
• General pseudo-random generators from weaker models of computation
• Incompressible functions, relative-error extractors, and the power of nondeterministic reductions (extended abstract)
• Hardness amplification within NP against deterministic algorithms
• Quantified Derandomization: How to Find Water in the Ocean
• scientific article; zbMATH DE number 2081094 (Why is no real title available?)
• The exact complexity of pseudorandom functions and the black-box natural proof barrier for bootstrapping results in computational complexity
• Randomness buys depth for approximate counting
• On uniformity and circuit lower bounds
• Towards a tight hardness-randomness connection between permanent and arithmetic circuit identity testing
• On linear-size pseudorandom generators and hardcore functions
• Structural lower bounds on black-box constructions of pseudorandom functions
• Randomness extraction in \(\mathsf{AC}^0\) and with small locality
• scientific article; zbMATH DE number 1689047 (Why is no real title available?)
• Constant-error pseudorandomness proofs from hardness require majority
• On derandomizing Yao's weak-to-strong OWF construction
• Uniform derandomization from pathetic lower bounds
• Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution

This page was built for publication: The complexity of constructing pseudorandom generators from hard functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1766819)