Pseudorandom generators without the XOR lemma

DOI10.1006/jcss.2000.1730zbMath1005.65006OpenAlexW1901622511WikidataQ124807825 ScholiaQ124807825MaRDI QIDQ5943089

Madhu Sudan, Luca Trevisan, Salil P. Vadhan

Publication date: 4 February 2003

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: http://nrs.harvard.edu/urn-3:HUL.InstRepos:4728405

zbMATH Keywords

pseudorandom number generationcircuit complexityerror correcting codeshardness amplificationpseudoergodic generator

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random number generation in numerical analysis (65C10) Complexity and performance of numerical algorithms (65Y20) Pseudo-random numbers; Monte Carlo methods (11K45)

Related Items (53)

Incompressible functions, relative-error extractors, and the power of nondeterministic reductions ⋮ Quantified Derandomization: How to Find Water in the Ocean ⋮ Reconstructive dispersers and hitting set generators ⋮ Can we locally compute sparse connected subgraphs? ⋮ Improved hardness amplification in NP ⋮ Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization ⋮ On building fine-grained one-way functions from strong average-case hardness ⋮ On locally decodable codes, self-correctable codes, and \(t\)-private PIR ⋮ List-decoding Barnes-Wall lattices ⋮ Pseudorandom generators for combinatorial checkerboards ⋮ Worst-Case to Average-Case Reductions for Subclasses of P ⋮ Hardness amplification within NP against deterministic algorithms ⋮ Erasures versus errors in local decoding and property testing ⋮ Improved List Decoding of Folded Reed-Solomon and Multiplicity Codes ⋮ Is it possible to improve Yao's XOR lemma using reductions that exploit the efficiency of their oracle? ⋮ Improved List-Decodability and List-Recoverability of Reed–Solomon Codes via Tree Packings ⋮ Memory-hard puzzles in the standard model with applications to memory-hard functions and resource-bounded locally decodable codes ⋮ Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\) ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Singleton-type bounds for list-decoding and list-recovery, and related results ⋮ Local List Recovery of High-Rate Tensor Codes and Applications ⋮ The inverse conjecture for the Gowers norm over finite fields in low characteristic ⋮ On derandomizing Yao's weak-to-strong OWF construction ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Weak derandomization of weak algorithms: explicit versions of Yao's lemma ⋮ Complexity of hard-core set proofs ⋮ Amplification and Derandomization without Slowdown ⋮ Isolation, matching, and counting uniform and nonuniform upper bounds ⋮ Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma ⋮ Unnamed Item ⋮ Foundations of Homomorphic Secret Sharing ⋮ Symmetric LDPC codes and local testing ⋮ Collapsing and separating completeness notions under average-case and worst-case hypotheses ⋮ Symmetric LDPC Codes and Local Testing ⋮ Local Property Reconstruction and Monotonicity ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Hardness amplification within NP ⋮ Pseudo-random generators for all hardnesses ⋮ Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification ⋮ Local algorithms for sparse spanning graphs ⋮ ON THE HARDNESS AGAINST CONSTANT-DEPTH LINEAR-SIZE CIRCUITS ⋮ Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification ⋮ Computational Randomness from Generalized Hardcore Sets ⋮ Typically-correct derandomization for small time and space ⋮ Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition ⋮ A combination of testability and decodability by tensor products ⋮ Mining circuit lower bound proofs for meta-algorithms ⋮ Direct Sum Testing

Cites Work

• Probabilistic encryption
• Advances in cryptology -- CRYPTO '85. Proceedings. (A Conference on the Theory and Application of Cryptographic techniques held at the University of California, Santa Barbara, August 18--22, 1985)
• On the power of two-point based sampling
• Highly resilient correctors for polynomials
• Modern cryptography, probabilistic proofs and pseudo-randomness
• Extracting randomness: A survey and new constructions
• \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
• Hardness vs randomness
• On the hardness of computing the permanent of random matrices
• Decoding of Reed Solomon codes beyond the error-correction bound
• Randomness vs time: Derandomization under a uniform assumption
• Randomness is linear in space
• Simulating BPP using a general weak random source
• Construction of extractors using pseudo-random generators (extended abstract)
• Pseudorandom generators without the XOR Lemma (extended abstract)
• Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses
• Random-Self-Reducibility of Complete Sets
• Extractors and pseudo-random generators with optimal seed length
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• A theory of the learnable
• Reconstructing Algebraic Functions from Mixed Data
• A Pseudorandom Generator from any One-way Function
• Computing with Very Weak Random Sources
• Improved decoding of Reed-Solomon and algebraic-geometry codes
• Worst-case hardness suffices for derandomization: A new method for hardness-randomness trade-offs
• Natural proofs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Pseudorandom generators without the XOR lemma