Paradigms for Unconditional Pseudorandom Generators

DOI10.1561/0400000109MaRDI QIDQ6149335zbMATH OpenOpenAlexFDO

Authors Pooya Hatami, William M. Hoza

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

• \(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\)
• BPP has subexponential time simulations unless EXPTIME has publishable proofs
• A combinatorial construction of almost-Ramanujan graphs using the zig-zag product
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A lower bound for read-once-only branching programs
• A new general derandomization method
• A new proof of Friedman's second eigenvalue theorem and its extension to random lifts
• A polynomial-time construction of a hitting set for read-once branching programs of width 3
• A primer on pseudorandom generators
• A proof of Alon’s second eigenvalue conjecture and related problems
• A Pseudorandom Generator from any One-way Function
• A satisfiability algorithm for \(\mathrm{AC}^0\)
• A simple proof of Bazzi's theorem
• A Simple Unpredictable Pseudo-Random Number Generator
• A slight sharpening of LMN
• An improved derandomization of the switching lemma
• An introduction to randomness extractors
• Analysis of Boolean Functions
• Approximate inclusion-exclusion
• Balls and bins: smaller hash families and faster evaluation
• Bounded Independence Fools Halfspaces
• Bounded independence plus noise fools products
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Bounds for Width Two Branching Programs
• BQP and the polynomial hierarchy
• Characterizing pseudoentropy and simplifying pseudorandom generator constructions
• Circuit lower bounds for MCSP from local pseudorandom generators
• Circuit minimization problem
• Communication Complexity
• Communication complexity
• Computational Complexity
• Concentration for limited independence via inequalities for the elementary symmetric polynomials
• Constant depth circuits, Fourier transform, and learnability
• Correlation bounds for poly-size \(\mathrm{AC}^0\) circuits with \(n^{1 - o(1)}\) symmetric gates
• Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
• Criticality of regular formulas
• Efficiency improvements in constructing pseudorandom generators from one-way functions
• Efficient approximation of product distributions
• Efficient construction of a small hitting set for combinatorial rectangles in high dimension
• Efficient Pseudorandom Generators from Exponentially Hard One-Way Functions
• Eigenvalues and expanders
• Error reduction for weighted PRGs against read once branching programs
• Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
• Expander graphs and gaps between primes
• Expander graphs and their applications
• Expander graphs in pure and applied mathematics
• Expander random walks: a Fourier-analytic approach
• Explicit construction of a small -net for linear threshold functions
• Explicit expanders of every degree and size
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• Explicit near-Ramanujan graphs of every degree
• Explicit, almost optimal, epsilon-balanced codes
• Extracting all the randomness and reducing the error in Trevisan's extractors
• Extracting randomness: A survey and new constructions
• Extractors and pseudorandom generators
• Families of finite sets in which no set is covered by the union of \(r\) others
• Finding the Median (Obliviously) with Bounded Space
• Fine-Grained Cryptography
• Fine-grained cryptography revisited
• Fine-grained derandomization: from problem-centric to resource-centric complexity
• Foundations of Cryptography
• Fourier bounds and pseudorandom generators for product tests
• Fractional pseudorandom generators from any fourier level
• Further scramblings of Marsaglia's \(\mathsf{xorshift}\) generators
• Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data
• Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
• Hardness and hierarchy theorems for probabilistic quasi-polynomial time
• Hardness vs randomness
• Hitting sets give two-sided derandomization of small space
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• scientific article; zbMATH DE number 1820017 (Why is no real title available?)
• scientific article; zbMATH DE number 6351503 (Why is no real title available?)
• scientific article; zbMATH DE number 3162894 (Why is no real title available?)
• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• scientific article; zbMATH DE number 1301964 (Why is no real title available?)
• scientific article; zbMATH DE number 1304314 (Why is no real title available?)
• scientific article; zbMATH DE number 1559537 (Why is no real title available?)
• scientific article; zbMATH DE number 1857655 (Why is no real title available?)
• scientific article; zbMATH DE number 7561734 (Why is no real title available?)
• scientific article; zbMATH DE number 7561753 (Why is no real title available?)
• scientific article; zbMATH DE number 7768373 (Why is no real title available?)
• scientific article; zbMATH DE number 7701432 (Why is no real title available?)
• Improved algorithms via approximations of probability distributions
• Improved hardness amplification in NP
• Improved pseudorandom generators for combinatorial rectangles
• Improved pseudorandom generators for depth 2 circuits
• Improved pseudorandom generators from pseudorandom multi-switching lemmas
• Improved pseudorandomness for unordered branching programs through local monotonicity
• In a world of \(\mathrm{P}=\mathrm{BPP}\)
• Interlacing families. I: Bipartite Ramanujan graphs of all degrees
• Learning Decision Trees Using the Fourier Spectrum
• Limitations of the Impagliazzo-Nisan-Wigderson pseudorandom generator against permutation branching programs
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Luby-Veličković-Wigderson revisited: improved correlation bounds and pseudorandom generators for depth-two circuits
• Matchings and covers in hypergraphs
• Mersenne twister
• More on bounded independence plus noise: pseudorandom generators for read-once polynomials
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• Natural proofs
• Near-optimal pseudorandom generators for constant-depth read-once formulas
• NP is as easy as detecting unique solutions
• On a packing and covering problem
• On coverings
• On deterministic approximation of DNF
• On polynomial approximations to \(\mathrm{AC}^0\)
• On the Correlation of Parity and Small-Depth Circuits
• On the distribution of the number of roots of polynomials and explicit weak designs
• On the Existence of Pseudorandom Generators
• On the Power of the Randomized Iterate
• On the second eigenvalue of a graph
• One way functions and pseudorandom generators
• Polylogarithmic independence can fool DNF formulas
• Polylogarithmic independence fools \(\mathrm{AC}^{0}\) circuits
• Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy
• Pseudo-random generators for all hardnesses
• Pseudodistributions that beat all pseudorandom generators (extended abstract)
• Pseudorandom bits for constant depth circuits
• Pseudorandom Bits for Constant‐Depth Circuits with Few Arbitrary Symmetric Gates
• Pseudorandom bits for polynomials
• Pseudorandom generators for group products, extended abstract
• Pseudorandom Generators for Read-Once Monotone Branching Programs
• Pseudorandom generators for regular branching programs
• Pseudorandom generators for space-bounded computation
• Pseudorandom generators for width-3 branching programs
• Pseudorandom generators from polarizing random walks
• Pseudorandom generators from regular one-way functions: new constructions with improved parameters
• Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates
• Pseudorandom generators without the XOR lemma
• Pseudorandom pseudo-distributions with near-optimal error for read-once branching programs
• Pseudorandom walks on regular digraphs and the RL vs. L problem
• Pseudorandomness
• Pseudorandomness and average-case complexity via uniform reductions
• Pseudorandomness and Fourier-growth bounds for width-3 branching programs
• Pseudorandomness for network algorithms
• Pseudorandomness for read-k DNF formulas
• Pseudorandomness for Read-Once Formulas
• Pseudorandomness for regular branching programs via Fourier analysis
• Pseudorandomness for width-2 branching programs
• Pseudorandomness from shrinkage
• Pseudorandomness via the discrete Fourier transform
• Ramanujan graphs
• Randomness buys depth for approximate counting
• Randomness is linear in space
• Randomness vs time: Derandomization under a uniform assumption
• Reducing the seed length in the Nisan-Wigderson generator
• Relations Among Complexity Measures
• RSA and Rabin Functions: Certain Parts are as Hard as the Whole
• Satisfiability and derandomization for small polynomial threshold circuits
• Simple and fast derandomization from very hard functions: eliminating randomness at almost no cost
• Simple constructions from (almost) regular one-way functions
• Simple Constructions of Almost k-wise Independent Random Variables
• Simple extractors for all min-entropies and a new pseudorandom generator
• Simple optimal hitting sets for small-success RL
• Simplified derandomization of BPP using a hitting set generator
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Small-Bias Spaces for Group Products
• Some geometric aspects of graphs and their eigenfunctions
• Some limitations of the sum of small-bias distributions
• Stable distributions, pseudorandom generators, embeddings, and data stream computation
• Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization
• TestU01
• The average sensitivity of bounded-depth circuits
• The randomized iterate, revisited -- almost linear seed length PRGs from a broader class of one-way functions
• The sum of \(D\) small-bias generators fools polynomials of degree \(D\)
• Theory of Cryptography
• Tight bounds on the Fourier spectrum of \(\mathsf{AC}^0\)
• Time-space tradeoffs for branching programs
• Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
• Unconditional pseudorandom generators for low degree polynomials
• Using Nondeterminism to Amplify Hardness
• Weak Random Sources, Hitting Sets, and BPP Simulations

Cited in

(4)

• Implications of better PRGs for permutation branching programs
• Fooling near-maximal decision trees
• Pseudorandomness of expander walks via Fourier analysis on groups
• On sums of INW pseudorandom generators

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6149335)