Nearly optimal pseudorandomness from hardness

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Randomized algorithms (68W20) Networks and circuits as models of computation; circuit complexity (68Q06)

Related Items (1)

Non-malleable codes with optimal rate for poly-size circuits

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Incompressible functions, relative-error extractors, and the power of nondeterministic reductions
Complexity of computation in finite fields
Derandomizing Arthur-Merlin games using hitting sets
Explicit constructions of linear-sized superconcentrators
Hardness vs randomness
Decoding of Reed Solomon codes beyond the error-correction bound
Relative expanders or weakly relatively Ramanujan graphs.
Entropy waves, the zig-zag graph product, and new constant-degree expanders
Linear-time list recovery of high-rate expander codes
Uniform hardness versus randomness tradeoffs for Arthur-Merlin games
2-source dispersers for \(n^{o(1)}\) entropy, and Ramsey graphs beating the Frankl-Wilson construction
Multi-point evaluation in higher dimensions
Improved bounds for quantified derandomization of constant-depth circuits and polynomials
Pseudorandomness for approximate counting and sampling
Extractors from Reed-Muller codes
A unified approach to deterministic encryption: new constructions and a connection to computational entropy
Modern Computer Algebra
A Unified Approach to Deterministic Encryption: New Constructions and a Connection to Computational Entropy
Metric Pseudoentropy: Characterizations, Transformations and Applications
Barriers in cryptography with weak, correlated and leaky sources
A Sample of Samplers: A Computational Perspective on Sampling
Small-Bias Probability Spaces: Efficient Constructions and Applications
Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
Property testing and its connection to learning and approximation
Fast Polynomial Factorization and Modular Composition
Condensed Unpredictability
Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes
Parallel Hashing via List Recoverability
The Complexity of Local List Decoding
Simple extractors for all min-entropies and a new pseudorandom generator
Extractor Codes
Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets
Linear time encodable and list decodable codes
Explicit Codes Achieving List Decoding Capacity: Error-Correction With Optimal Redundancy
Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data
Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
Simple Constructions of Almost k-wise Independent Random Variables
Relations Among Complexity Measures
Reconstructing Algebraic Functions from Mixed Data
A Pseudorandom Generator from any One-way Function
Tiny families of functions with random properties: A quality-size trade-off for hashing
High-Rate Locally Correctable and Locally Testable Codes with Sub-Polynomial Query Complexity
Locally Testable and Locally Correctable Codes approaching the Gilbert-Varshamov Bound
Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators
For-All Sparse Recovery in Near-Optimal Time
Pseudorandom Generators with Optimal Seed Length for Non-Boolean Poly-Size Circuits
Explicit, almost optimal, epsilon-balanced codes
Local List Recovery of High-Rate Tensor Codes and Applications
Memory Delegation
Bootstrapping results for threshold circuits “just beyond” known lower bounds
Quantified derandomization of linear threshold circuits
List Decoding with Double Samplers
On derandomizing algorithms that err extremely rarely
ℓ2/ℓ2-Foreach Sparse Recovery with Low Risk
Pseudorandomness when the odds are against you
Derandomization in Cryptography
Conditional Computational Entropy, or Toward Separating Pseudoentropy from Compressibility
Extractors and pseudorandom generators
Extracting Randomness via Repeated Condensing
Class of constructive asymptotically good algebraic codes
Locally Decodable Codes
Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
Extracting all the randomness and reducing the error in Trevisan's extractors
Pseudo-random generators for all hardnesses
Pseudorandom generators without the XOR lemma

This page was built for publication: Nearly optimal pseudorandomness from hardness