The complexity of constructing pseudorandom generators from hard functions

Pseudo-random numbers; Monte Carlo methods (11K45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

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

(40)

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

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)