Paradigms for Unconditional Pseudorandom Generators (Q6149335)

scientific article; zbMATH DE number 7812873

Language	Label	Description	Also known as
English	Paradigms for Unconditional Pseudorandom Generators	scientific article; zbMATH DE number 7812873

Statements

instance of

scholarly article

0 references

title

Paradigms for Unconditional Pseudorandom Generators (English)

0 references

0 references

0 references

0 references

Foundations and Trends® in Theoretical Computer Science

0 references

publication date

5 March 2024

0 references

Mathematics Subject Classification ID

0 references

0 references

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1561/0400000109

0 references

OpenAlex ID

W4391927103

0 references

cites work

BQP and the polynomial hierarchy

0 references

RSA and Rabin Functions: Certain Parts are as Hard as the Whole

0 references

Eigenvalues and expanders

0 references

Explicit expanders of every degree and size

0 references

A fast and simple randomized parallel algorithm for the maximal independent set problem

0 references

Simple Constructions of Almost k-wise Independent Random Variables

0 references

A new general derandomization method

0 references

Weak Random Sources, Hitting Sets, and BPP Simulations

0 references

Q4247197

0 references

Computational Complexity

0 references

$BPP$ has subexponential time simulations unless $EXPTIME$ has publishable proofs

0 references

A lower bound for read-once-only branching programs

0 references

Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs

0 references

Bounded-width polynomial-size branching programs recognize exactly those languages in $NC^ 1$

0 references

Polylogarithmic Independence Can Fool DNF Formulas

0 references

Time-space tradeoffs for branching programs

0 references

Finding the Median (Obliviously) with Bounded Space

0 references

A Combinatorial Construction of Almost-Ramanujan Graphs Using the Zig-Zag Product

0 references

A Simple Unpredictable Pseudo-Random Number Generator

0 references

How to Generate Cryptographically Strong Sequences of Pseudorandom Bits

0 references

Q3191575

0 references

Pseudorandomness for Read-Once Formulas

0 references

Pseudorandom Bits for Polynomials

0 references

The average sensitivity of bounded-depth circuits

0 references

A new proof of Friedman's second eigenvalue theorem and its extension to random lifts

0 references

Bounds for Width Two Branching Programs

0 references

Polylogarithmic independence fools AC 0 circuits

0 references

Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs

0 references

Pseudorandom Generators for Regular Branching Programs

0 references

Q4251044

0 references

Hardness and hierarchy theorems for probabilistic quasi-polynomial time

0 references

Q5002697

0 references

Balls and Bins: Smaller Hash Families and Faster Evaluation

0 references

Improved algorithms via approximations of probability distributions

0 references

Fractional pseudorandom generators from any fourier level

0 references

Q5204828

0 references

Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates

0 references

Improved pseudorandomness for unordered branching programs through local monotonicity

0 references

Q5092476

0 references

Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization

0 references

Simple and fast derandomization from very hard functions: eliminating randomness at almost no cost

0 references

Q5040833

0 references

Circuit Lower Bounds for MCSP from Local Pseudorandom Generators

0 references

Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity

0 references

Expander graphs and gaps between primes

0 references

Error reduction for weighted PRGs against read once branching programs

0 references

Expander random walks: a Fourier-analytic approach

0 references

Improved Pseudorandom Generators for Depth 2 Circuits

0 references

Fine-Grained Cryptography

0 references

Bounded Independence Fools Halfspaces

0 references

Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data

0 references

Near-optimal pseudorandom generators for constant-depth read-once formulas

0 references

Q5092453

0 references

Pseudorandom Generators for Read-Once Monotone Branching Programs

0 references

Fine-grained cryptography revisited

0 references

Families of finite sets in which no set is covered by the union of $r$ others

0 references

Efficient approximation of product distributions

0 references

Q3191596

0 references

Some geometric aspects of graphs and their eigenfunctions

0 references

A proof of Alon’s second eigenvalue conjecture and related problems

0 references

Matchings and covers in hypergraphs

0 references

Foundations of Cryptography

0 references

Q3585016

0 references

In a World of P=BPP

0 references

On the Existence of Pseudorandom Generators

0 references

Simplified Derandomization of BPP Using a Hitting Set Generator

0 references

Pseudorandomness via the Discrete Fourier Transform

0 references

Q5857609

0 references

Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes

0 references

Efficient Pseudorandom Generators from Exponentially Hard One-Way Functions

0 references

On the Power of the Randomized Iterate

0 references

Efficiency Improvements in Constructing Pseudorandom Generators from One-Way Functions

0 references

Bounded Independence Plus Noise Fools Products

0 references

On polynomial approximations to AC

0 references

On the distribution of the number of roots of polynomials and explicit weak designs

0 references

A slight sharpening of LMN

0 references

On the Correlation of Parity and Small-Depth Circuits

0 references

A Pseudorandom Generator from any One-way Function

0 references

Using Nondeterminism to Amplify Hardness

0 references

Theory of Cryptography

0 references

Expander graphs and their applications

0 references

Q6090903

0 references

Q6161058

0 references

Simple Optimal Hitting Sets for Small-Success RL

0 references

Q5743451

0 references

Pseudorandomness from Shrinkage

0 references

Pseudorandomness for network algorithms

0 references

Reducing the seed length in the Nisan-Wigderson generator

0 references

Q4526985

0 references

Randomness vs time: Derandomization under a uniform assumption

0 references

Stable distributions, pseudorandom generators, embeddings, and data stream computation

0 references

Circuit minimization problem

0 references

Q5009542

0 references

An improved derandomization of the switching lemma

0 references

Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses

0 references

Pseudorandom generators for group products

0 references

Learning Decision Trees Using the Fourier Spectrum

0 references

TestU01

0 references

Fourier bounds and pseudorandom generators for product tests

0 references

Q4602401

0 references

Q5140841

0 references

One way functions and pseudorandom generators

0 references

Efficient construction of a small hitting set for combinatorial rectangles in high dimension

0 references

Constant depth circuits, Fourier transform, and learnability

0 references

Approximate inclusion-exclusion

0 references

Q3002801

0 references

Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 − o(1) Symmetric Gates

0 references

Improved pseudorandom generators for combinatorial rectangles

0 references

Improved hardness amplification in NP

0 references

Ramanujan graphs

0 references

Expander graphs in pure and applied mathematics

0 references

On deterministic approximation of DNF

0 references

Interlacing families. I: Bipartite Ramanujan graphs of all degrees

0 references

Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators

0 references

Mersenne twister

0 references

Simple constructions from (almost) regular one-way functions

0 references

Pseudorandom generators for width-3 branching programs

0 references

Small-Bias Spaces for Group Products

0 references

Pseudorandom Generators for Polynomial Threshold Functions

0 references

Q4788614

0 references

Explicit near-Ramanujan graphs of every degree

0 references

Existence and explicit constructions of $q+1$ regular Ramanujan graphs for every prime power $q$

0 references

Small-Bias Probability Spaces: Efficient Constructions and Applications

0 references

On the second eigenvalue of a graph

0 references

Pseudorandom bits for constant depth circuits

0 references

Pseudorandom generators for space-bounded computation

0 references

Extracting randomness: A survey and new constructions

0 references

Hardness vs randomness

0 references

Randomness is linear in space

0 references

Analysis of Boolean Functions

0 references

Communication complexity

0 references

Relations Among Complexity Measures

0 references

Limitations of the Impagliazzo-Nisan-Wigderson pseudorandom generator against permutation branching programs

0 references

Pseudodistributions that beat all pseudorandom generators (extended abstract)

0 references

Explicit Construction of a Small $\epsilon$-Net for Linear Threshold Functions

0 references

Communication Complexity

0 references

Extracting all the randomness and reducing the error in Trevisan's extractors

0 references

Lower bounds on the size of bounded depth circuits over a complete basis with logical addition

0 references

Natural proofs

0 references

A Simple Proof of Bazzi’s Theorem

0 references

Pseudorandomness for Regular Branching Programs via Fourier Analysis

0 references

Pseudorandom walks on regular digraphs and the RL vs. L problem

0 references

On a packing and covering problem

0 references

Criticality of regular formulas

0 references

$\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})$

0 references

On coverings

0 references

Q5009555

0 references

Q5875501

0 references

Pseudorandomness for read-k DNF formulas

0 references

Q3152800

0 references

An Introduction to Randomness Extractors

0 references

Simple extractors for all min-entropies and a new pseudorandom generator

0 references

Explicit, almost optimal, epsilon-balanced codes

0 references

A Polynomial-Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3

0 references

Q4591372

0 references

Q3281059

0 references

Pseudorandom generators without the XOR lemma

0 references

Q5111145

0 references

Probabilistic polynomials, AC$^ 0$ functions and the polynomial-time hierarchy

0 references

Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy

0 references

Extractors and pseudorandom generators

0 references

Pseudorandomness and average-case complexity via uniform reductions

0 references

Pseudo-random generators for all hardnesses

0 references

Characterizing pseudoentropy and simplifying pseudorandom generator constructions

0 references

Pseudorandomness

0 references

NP is as easy as detecting unique solutions

0 references

Further scramblings of Marsaglia's $\mathsf{xorshift}$ generators

0 references

Pseudorandom Bits for Constant‐Depth Circuits with Few Arbitrary Symmetric Gates

0 references

The sum of $D$ small-bias generators fools polynomials of degree $D$

0 references

Randomness buys depth for approximate counting

0 references

Q3762226

0 references

The Randomized Iterate, Revisited - Almost Linear Seed Length PRGs from a Broader Class of One-Way Functions

0 references

Pseudorandom generators from regular one-way functions: new constructions with improved parameters

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:6149335