Nearly optimal pseudorandomness from hardness
type: Item
instance of: scholarly article
title: Nearly optimal pseudorandomness from hardness
DOI: 10.1145/3555307
author: Dean Doron
author: Dana Moshkovitz
author: Justin Oh
author: David Zuckerman
published in: Journal of the ACM
publication date: 2024-06-06T00:00:00Z
Mathematics Subject Classification ID: 68P30
Mathematics Subject Classification ID: 68Q06
Mathematics Subject Classification ID: 68W20
zbMATH DE Number: 7860936
zbMATH Keywords: pseudorandom generators
zbMATH Keywords: pseudoentropy
zbMATH Keywords: quantified derandomization
zbMATH Keywords: list recovery
zbMATH Keywords: local list decoding
MaRDI profile type: MaRDI publication profile
cites work: Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
cites work: Q4252735
cites work: Simple Constructions of Almost k-wise Independent Random Variables
cites work: Incompressible functions, relative-error extractors, and the power of nondeterministic reductions
cites work: Reconstructing Algebraic Functions from Mixed Data
cites work: Pseudorandomness when the odds are against you
cites work: Pseudorandom Generators with Optimal Seed Length for Non-Boolean Poly-Size Circuits
cites work: Q4370034
cites work: Derandomization in Cryptography
cites work: 2-source dispersers for \(n^{o(1)}\) entropy, and Ramsey graphs beating the Frankl-Wilson construction
cites work: Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
cites work: Bootstrapping results for threshold circuits “just beyond” known lower bounds
cites work: Memory Delegation
cites work: List Decoding with Double Samplers
cites work: Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data
cites work: Q3191596
cites work: Relative expanders or weakly relatively Ramanujan graphs.
cites work: A unified approach to deterministic encryption: new constructions and a connection to computational entropy
cites work: A Unified Approach to Deterministic Encryption: New Constructions and a Connection to Computational Entropy
cites work: Explicit constructions of linear-sized superconcentrators
cites work: Complexity of computation in finite fields
cites work: For-All Sparse Recovery in Near-Optimal Time
cites work: ℓ2/ℓ2-Foreach Sparse Recovery with Low Risk
cites work: A Sample of Samplers: A Computational Perspective on Sampling
cites work: Property testing and its connection to learning and approximation
cites work: On derandomizing algorithms that err extremely rarely
cites work: Tiny families of functions with random properties: A quality-size trade-off for hashing
cites work: Q4440439
cites work: Locally Testable and Locally Correctable Codes approaching the Gilbert-Varshamov Bound
cites work: Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets
cites work: Linear time encodable and list decodable codes
cites work: Explicit Codes Achieving List Decoding Capacity: Error-Correction With Optimal Redundancy
cites work: Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes
cites work: The Complexity of Local List Decoding
cites work: Uniform hardness versus randomness tradeoffs for Arthur-Merlin games
cites work: Parallel Hashing via List Recoverability
cites work: A Pseudorandom Generator from any One-way Function
cites work: Local List Recovery of High-Rate Tensor Codes and Applications
cites work: Linear-time list recovery of high-rate expander codes
cites work: Conditional Computational Entropy, or Toward Separating Pseudoentropy from Compressibility
cites work: Q4526985
cites work: Q5417695
cites work: Class of constructive asymptotically good algebraic codes
cites work: Fast Polynomial Factorization and Modular Composition
cites work: Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
cites work: High-Rate Locally Correctable and Locally Testable Codes with Sub-Polynomial Query Complexity
cites work: Derandomizing Arthur-Merlin games using hitting sets
cites work: Q5875498
cites work: Small-Bias Probability Spaces: Efficient Constructions and Applications
cites work: Hardness vs randomness
cites work: Relations Among Complexity Measures
cites work: Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators
cites work: Extracting all the randomness and reducing the error in Trevisan's extractors
cites work: Extracting Randomness via Repeated Condensing
cites work: Entropy waves, the zig-zag graph product, and new constant-degree expanders
cites work: Q4607923
cites work: Simple extractors for all min-entropies and a new pseudorandom generator
cites work: Pseudorandomness for approximate counting and sampling
cites work: Q3549642
cites work: Metric Pseudoentropy: Characterizations, Transformations and Applications

Nearly optimal pseudorandomness from hardness (cites work)
cites work: Condensed Unpredictability

Nearly optimal pseudorandomness from hardness (cites work)
cites work: Decoding of Reed Solomon codes beyond the error-correction bound

Nearly optimal pseudorandomness from hardness (cites work)
cites work: Pseudorandom generators without the XOR lemma

Nearly optimal pseudorandomness from hardness (cites work)
cites work: Explicit, almost optimal, epsilon-balanced codes

Nearly optimal pseudorandomness from hardness (cites work)
cites work: Extractor Codes

Nearly optimal pseudorandomness from hardness (cites work)
cites work: Extractors from Reed-Muller codes

Nearly optimal pseudorandomness from hardness (cites work)
cites work: Quantified derandomization of linear threshold circuits

Nearly optimal pseudorandomness from hardness (cites work)
cites work: Improved bounds for quantified derandomization of constant-depth circuits and polynomials

Nearly optimal pseudorandomness from hardness (cites work)
cites work: Extractors and pseudorandom generators

Nearly optimal pseudorandomness from hardness (cites work)
cites work: Pseudo-random generators for all hardnesses

Nearly optimal pseudorandomness from hardness (cites work)
cites work: Multi-point evaluation in higher dimensions

Nearly optimal pseudorandomness from hardness (cites work)
cites work: Modern computer algebra

Nearly optimal pseudorandomness from hardness (cites work)
cites work: Barriers in cryptography with weak, correlated and leaky sources

Nearly optimal pseudorandomness from hardness (cites work)
cites work: Q5368736

Nearly optimal pseudorandomness from hardness (cites work)
cites work: Locally decodable codes

Nearly optimal pseudorandomness from hardness (cites work)
cites work: Q4372786

Nearly optimal pseudorandomness from hardness (cites work)
cites work: Q3002782