Paradigms for Unconditional Pseudorandom Generators
From MaRDI portal
Publication:6149335
DOI10.1561/0400000109OpenAlexW4391927103MaRDI QIDQ6149335
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
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 0 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