Pseudorandom bits for constant depth circuits

Cites Work

Probabilistic encryption
$\Sigma_ 1^ 1$-formulae on finite structures
How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
Alternation
The polynomial-time hierarchy
Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
Pseudorandom number generation and space complexity

Cited In (47)

Improving the space-bounded version of Muchnik's conditional complexity theorem via ``naive derandomization
Expander-Based Cryptography Meets Natural Proofs
Not all FPRASs are equal: demystifying FPRASs for DNF-counting
Pseudorandom generators for $\mathrm{CC}^0[p]$ and the Fourier spectrum of low-degree polynomials over finite fields
Pseudorandom generators for combinatorial checkerboards
A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus]$ via the Coin Problem
An Almost m-wise Independent Random Permutation of the Cube
Constructive separations and their consequences
Bounded-depth circuits cannot sample good codes
Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 − o(1) Symmetric Gates
Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds
Paradigms for Unconditional Pseudorandom Generators
Bit commitment using pseudorandomness
Extremal set theory and LWE based access structure hiding verifiable secret sharing with malicious-majority and free verification
Expander-based cryptography meets natural proofs
Randomness-efficient non-interactive zero knowledge
Large sets in $\mathrm{AC}^{0}$ have many strings with low Kolmogorov complexity
Hardness vs randomness
Pseudorandom generators, typically-correct derandomization, and circuit lower bounds
An optimal approximation algorithm for Bayesian inference
On algorithmic statistics for space-bounded algorithms
Negation-limited formulas
Title not available (Why is that?)
Explicit list-decodable codes with optimal rate for computationally bounded channels
Natural proofs
Counting Solutions to Polynomial Systems via Reductions
Title not available (Why is that?)
Title not available (Why is that?)
Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
Quantified Derandomization: How to Find Water in the Ocean
Title not available (Why is that?)
Title not available (Why is that?)
Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits
$\mathrm{AC}^{0}\circ \mathrm{MOD}_{2}$ lower bounds for the Boolean inner product
Randomness vs time: Derandomization under a uniform assumption
DNF sparsification and a faster deterministic counting algorithm
Title not available (Why is that?)
Generation of all randomizations using circuits
Near-optimal pseudorandom generators for constant-depth read-once formulas
Title not available (Why is that?)
Fooling Polytopes
On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions
Small-bias is not enough to hit read-once CNF
Title not available (Why is that?)
Uniform derandomization from pathetic lower bounds
McCulloch-Pitts Brains and Pseudorandom Functions
A quasi-polynomial-time algorithm for sampling words from a context-free language

This page was built for publication: Pseudorandom bits for constant depth circuits

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