Pseudorandom bits for constant depth circuits
From MaRDI portal
Publication:808707
DOI10.1007/BF01375474zbMath0732.68056OpenAlexW2023915883MaRDI QIDQ808707
Publication date: 1991
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01375474
NPcomplexity class AMpseudo-random bit generatorsuniform family of circuits of polynomial size and constant depth
Related Items (42)
Expander-based cryptography meets natural proofs ⋮ Hardness vs randomness ⋮ Large sets in \(\mathrm{AC}^{0}\) have many strings with low Kolmogorov complexity ⋮ Quantified Derandomization: How to Find Water in the Ocean ⋮ Fooling Polytopes ⋮ A quasi-polynomial-time algorithm for sampling words from a context-free language ⋮ DNF sparsification and a faster deterministic counting algorithm ⋮ Randomness-efficient non-interactive zero knowledge ⋮ \(\mathrm{AC}^{0}\circ \mathrm{MOD}_{2}\) lower bounds for the Boolean inner product ⋮ Uniform derandomization from pathetic lower bounds ⋮ Pseudorandom generators for \(\mathrm{CC}^0[p\) and the Fourier spectrum of low-degree polynomials over finite fields] ⋮ Pseudorandom generators for combinatorial checkerboards ⋮ On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions ⋮ An optimal approximation algorithm for Bayesian inference ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Unnamed Item ⋮ Pseudorandom generators, typically-correct derandomization, and circuit lower bounds ⋮ Unnamed Item ⋮ Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds ⋮ Counting Solutions to Polynomial Systems via Reductions ⋮ McCulloch-Pitts Brains and Pseudorandom Functions ⋮ Extremal set theory and LWE based access structure hiding verifiable secret sharing with malicious-majority and free verification ⋮ Small-bias is not enough to hit read-once CNF ⋮ Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs ⋮ Bounded-depth circuits cannot sample good codes ⋮ Improving the space-bounded version of Muchnik's conditional complexity theorem via ``naive derandomization ⋮ Not all FPRASs are equal: demystifying FPRASs for DNF-counting ⋮ Unnamed Item ⋮ Natural proofs ⋮ Explicit list-decodable codes with optimal rate for computationally bounded channels ⋮ Negation-limited formulas ⋮ A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus$ via the Coin Problem] ⋮ On algorithmic statistics for space-bounded algorithms ⋮ Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 − o(1) Symmetric Gates ⋮ Unnamed Item ⋮ An Almost m-wise Independent Random Permutation of the Cube ⋮ Expander-Based Cryptography Meets Natural Proofs ⋮ Near-optimal pseudorandom generators for constant-depth read-once formulas ⋮ Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Randomness vs time: Derandomization under a uniform assumption
Cites Work
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- Probabilistic encryption
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- The polynomial-time hierarchy
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- Pseudorandom number generation and space complexity
- Alternation
This page was built for publication: Pseudorandom bits for constant depth circuits
