Pseudorandom bits for constant depth circuits
From MaRDI portal
Publication:808707
Recommendations
Cites work
- Alternation
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- Probabilistic encryption
- Pseudorandom number generation and space complexity
- The polynomial-time hierarchy
- \(\Sigma_ 1^ 1\)-formulae on finite structures
Cited in
(49)- Paradigms for Unconditional Pseudorandom Generators
- Extremal set theory and LWE based access structure hiding verifiable secret sharing with malicious-majority and free verification
- scientific article; zbMATH DE number 7650416 (Why is no real title available?)
- Expander-based cryptography meets natural proofs
- Hardness vs randomness
- Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
- Quantified Derandomization: How to Find Water in the Ocean
- More on bounded independence plus noise: pseudorandom generators for read-once polynomials
- Fooling Polytopes
- scientific article; zbMATH DE number 3976358 (Why is no real title available?)
- Pseudorandom generators, typically-correct derandomization, and circuit lower bounds
- Uniform derandomization from pathetic lower bounds
- DNF sparsification and a faster deterministic counting algorithm
- An Almost m-wise Independent Random Permutation of the Cube
- A quasi-polynomial-time algorithm for sampling words from a context-free language
- Correlation bounds for poly-size \(\mathrm{AC}^0\) circuits with \(n^{1 - o(1)}\) symmetric gates
- Expander-Based Cryptography Meets Natural Proofs
- Explicit list-decodable codes with optimal rate for computationally bounded channels
- Average-case lower bounds and satisfiability algorithms for small threshold circuits
- Pseudorandom generators for \(\mathrm{CC}^0[p]\) and the Fourier spectrum of low-degree polynomials over finite fields
- Pseudorandom generators for combinatorial checkerboards
- An optimal approximation algorithm for Bayesian inference
- Counting solutions to polynomial systems via reductions
- scientific article; zbMATH DE number 7009617 (Why is no real title available?)
- Luby-Veličković-Wigderson revisited: improved correlation bounds and pseudorandom generators for depth-two circuits
- A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus]$ via the Coin Problem
- Not all FPRASs are equal: demystifying FPRASs for DNF-counting
- Negation-limited formulas
- Randomness-efficient non-interactive zero knowledge
- On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions
- \(\mathrm{AC}^{0}\circ \mathrm{MOD}_{2}\) lower bounds for the Boolean inner product
- scientific article; zbMATH DE number 7250141 (Why is no real title available?)
- scientific article; zbMATH DE number 2081094 (Why is no real title available?)
- Pseudorandom Bits for Constant‐Depth Circuits with Few Arbitrary Symmetric Gates
- scientific article; zbMATH DE number 7528580 (Why is no real title available?)
- scientific article; zbMATH DE number 7650112 (Why is no real title available?)
- Near-optimal pseudorandom generators for constant-depth read-once formulas
- Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds
- Bounded-depth circuits cannot sample good codes
- Natural proofs
- Small-bias is not enough to hit read-once CNF
- Constructive separations and their consequences
- Randomness buys depth for approximate counting
- Bit commitment using pseudorandomness
- McCulloch-Pitts brains and pseudorandom functions
- Large sets in \(\mathrm{AC}^{0}\) have many strings with low Kolmogorov complexity
- scientific article; zbMATH DE number 1833418 (Why is no real title available?)
- Generation of all randomizations using circuits
- Randomness vs time: Derandomization under a uniform assumption
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)
