Paradigms for Unconditional Pseudorandom Generators

DOI10.1561/0400000109OpenAlexW4391927103MaRDI QIDQ6149335

William M. Hoza, Pooya Hatami

Publication date: 5 March 2024

Published in: Foundations and Trends® in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1561/0400000109

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

• Relations Among Complexity Measures
• Mersenne twister
• A Pseudorandom Generator from any One-way Function
• Weak Random Sources, Hitting Sets, and BPP Simulations
• On the Existence of Pseudorandom Generators
• Learning Decision Trees Using the Fourier Spectrum
• Foundations of Cryptography
• On the distribution of the number of roots of polynomials and explicit weak designs
• Pseudorandomness via the Discrete Fourier Transform
• On polynomial approximations to AC
• Bounded Independence Plus Noise Fools Products
• Efficient approximation of product distributions
• Explicit, almost optimal, epsilon-balanced codes
• Circuit Lower Bounds for MCSP from Local Pseudorandom Generators
• Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization
• Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates
• Criticality of regular formulas
• Fourier bounds and pseudorandom generators for product tests
• Near-optimal pseudorandom generators for constant-depth read-once formulas
• Simple Optimal Hitting Sets for Small-Success RL
• Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs
• Explicit near-Ramanujan graphs of every degree
• Analysis of Boolean Functions
• On the Correlation of Parity and Small-Depth Circuits
• Pseudorandom generators for width-3 branching programs
• Communication Complexity
• Improved pseudorandomness for unordered branching programs through local monotonicity
• Pseudorandomness for read-k DNF formulas
• Pseudorandomness from Shrinkage
• The Randomized Iterate, Revisited - Almost Linear Seed Length PRGs from a Broader Class of One-Way Functions
• Computational Complexity
• Bounded Independence Fools Halfspaces
• Explicit Construction of a Small $\epsilon$-Net for Linear Threshold Functions
• Characterizing pseudoentropy and simplifying pseudorandom generator constructions
• Pseudorandom generators for group products
• Pseudorandom Bits for Constant‐Depth Circuits with Few Arbitrary Symmetric Gates
• Extractors and pseudorandom generators
• Using Nondeterminism to Amplify Hardness
• Pseudorandomness for Read-Once Formulas
• A Polynomial-Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3
• Theory of Cryptography
• Natural proofs
• Extracting all the randomness and reducing the error in Trevisan's extractors
• Pseudo-random generators for all hardnesses
• Fine-grained cryptography revisited
• Pseudorandom generators without the XOR lemma
• Expander random walks: a Fourier-analytic approach
• An improved derandomization of the switching lemma
• Simple and fast derandomization from very hard functions: eliminating randomness at almost no cost
• Pseudorandom Generators for Read-Once Monotone Branching Programs
• Fractional pseudorandom generators from any fourier level
• Error reduction for weighted PRGs against read once branching programs
• Pseudodistributions that beat all pseudorandom generators (extended abstract)
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The average sensitivity of bounded-depth circuits
• Randomness buys depth for approximate counting
• The sum of \(D\) small-bias generators fools polynomials of degree \(D\)
• Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy
• Further scramblings of Marsaglia's \(\mathsf{xorshift}\) generators
• Pseudorandom bits for constant depth circuits
• Improved hardness amplification in NP
• Reducing the seed length in the Nisan-Wigderson generator
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• On a packing and covering problem
• Communication complexity
• Families of finite sets in which no set is covered by the union of \(r\) others
• NP is as easy as detecting unique solutions
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• One way functions and pseudorandom generators
• A lower bound for read-once-only branching programs
• Ramanujan graphs
• Eigenvalues and expanders
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Approximate inclusion-exclusion
• On the second eigenvalue of a graph
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• Pseudorandom generators for space-bounded computation
• Some geometric aspects of graphs and their eigenfunctions
• \(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\)
• Extracting randomness: A survey and new constructions
• \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
• Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
• Hardness vs randomness
• Efficient construction of a small hitting set for combinatorial rectangles in high dimension
• Improved algorithms via approximations of probability distributions
• A slight sharpening of LMN
• Time-space tradeoffs for branching programs
• Randomness vs time: Derandomization under a uniform assumption
• Matchings and covers in hypergraphs
• Improved pseudorandom generators for combinatorial rectangles
• Randomness is linear in space
• On deterministic approximation of DNF
• Explicit expanders of every degree and size
• Interlacing families. I: Bipartite Ramanujan graphs of all degrees
• On coverings
• Pseudorandomness and average-case complexity via uniform reductions
• Pseudorandom generators from regular one-way functions: new constructions with improved parameters
• Limitations of the Impagliazzo-Nisan-Wigderson pseudorandom generator against permutation branching programs
• Simple constructions from (almost) regular one-way functions
• Pseudorandomness for network algorithms
• Hardness and hierarchy theorems for probabilistic quasi-polynomial time
• Fine-Grained Cryptography
• Balls and Bins: Smaller Hash Families and Faster Evaluation
• Pseudorandom Generators for Polynomial Threshold Functions
• Efficiency Improvements in Constructing Pseudorandom Generators from One-Way Functions
• Pseudorandomness for Regular Branching Programs via Fourier Analysis
• Pseudorandomness
• BQP and the polynomial hierarchy
• Pseudorandom walks on regular digraphs and the RL vs. L problem
• A Simple Proof of Bazzi’s Theorem
• An Introduction to Randomness Extractors
• A Combinatorial Construction of Almost-Ramanujan Graphs Using the Zig-Zag Product
• Pseudorandom Bits for Polynomials
• Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 − o(1) Symmetric Gates
• Simplified Derandomization of BPP Using a Hitting Set Generator
• In a World of P=BPP
• Expander graphs in pure and applied mathematics
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Constant depth circuits, Fourier transform, and learnability
• Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
• Pseudorandom Generators for Regular Branching Programs
• Circuit minimization problem
• On the Power of the Randomized Iterate
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• A new proof of Friedman's second eigenvalue theorem and its extension to random lifts
• Finding the Median (Obliviously) with Bounded Space
• Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes
• Stable distributions, pseudorandom generators, embeddings, and data stream computation
• Expander graphs and their applications
• A proof of Alon’s second eigenvalue conjecture and related problems
• Expander graphs and gaps between primes
• Simple extractors for all min-entropies and a new pseudorandom generator
• TestU01
• Polylogarithmic independence fools AC ⁰ circuits
• Improved Pseudorandom Generators for Depth 2 Circuits
• Efficient Pseudorandom Generators from Exponentially Hard One-Way Functions
• Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data
• Small-Bias Spaces for Group Products
• Polylogarithmic Independence Can Fool DNF Formulas
• Bounds for Width Two Branching Programs
• A Simple Unpredictable Pseudo-Random Number Generator
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
• RSA and Rabin Functions: Certain Parts are as Hard as the Whole
• A new general derandomization method
• Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
• Simple Constructions of Almost k-wise Independent Random Variables

This page was built for publication: Paradigms for Unconditional Pseudorandom Generators