Improved pseudorandom generators from pseudorandom multi-switching lemmas
From MaRDI portal
Recommendations
- scientific article; zbMATH DE number 7528580
- Luby-Veličković-Wigderson revisited: improved correlation bounds and pseudorandom generators for depth-two circuits
- Pseudorandomness from shrinkage
- Near-optimal pseudorandom generators for constant-depth read-once formulas
- Improved pseudorandom generators for depth 2 circuits
Cites work
- scientific article; zbMATH DE number 1256716 (Why is no real title available?)
- scientific article; zbMATH DE number 524117 (Why is no real title available?)
- scientific article; zbMATH DE number 6861917 (Why is no real title available?)
- scientific article; zbMATH DE number 1833418 (Why is no real title available?)
- scientific article; zbMATH DE number 7250141 (Why is no real title available?)
- scientific article; zbMATH DE number 5485586 (Why is no real title available?)
- A polynomial-time construction of a hitting set for read-once branching programs of width 3
- A satisfiability algorithm for \(\mathrm{AC}^0\)
- A simple proof of Bazzi's theorem
- An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
- Approximate inclusion-exclusion
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- BQP and the polynomial hierarchy
- Constant depth circuits, Fourier transform, and learnability
- Correlation bounds for poly-size \(\mathrm{AC}^0\) circuits with \(n^{1 - o(1)}\) symmetric gates
- DNF sparsification and a faster deterministic counting algorithm
- Estimation of certain exponential sums arising in complexity theory
- Exponential lower bounds for the pigeonhole principle
- Hardness vs randomness
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- Improved pseudorandom generators for depth 2 circuits
- Lower bounds for recognizing small cliques on CRCW PRAM's
- Luby-Veličković-Wigderson revisited: improved correlation bounds and pseudorandom generators for depth-two circuits
- Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
- Near-optimal small-depth lower bounds for small distance connectivity
- Non-malleable codes
- Non-malleable codes and extractors for small-depth circuits, and affine functions
- Norms, XOR lemmas, and lower bounds for polynomials and protocols
- On beating the hybrid argument
- On derandomizing algorithms that err extremely rarely
- On deterministic approximation of DNF
- On the Correlation of Parity and Small-Depth Circuits
- On the power of small-depth computation
- On the power of small-depth threshold circuits
- Parity, circuits, and the polynomial-time hierarchy
- Poly-logarithmic Frege depth lower bounds via an expander switching lemma
- Polylogarithmic independence can fool DNF formulas
- Polylogarithmic independence fools \(\mathrm{AC}^{0}\) circuits
- Pseudorandom Bits for Constant‐Depth Circuits with Few Arbitrary Symmetric Gates
- Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates
- Pseudorandom bits for constant depth circuits
- Pseudorandom bits for polynomials
- Pseudorandom generators for low degree polynomials
- Pseudorandomness from shrinkage
- Random oracles separate PSPACE from the polynomial-time hierarchy
- Reducing the complexity of reductions
- Simple Constructions of Almost k-wise Independent Random Variables
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- The sum of \(D\) small-bias generators fools polynomials of degree \(D\)
- Tight bounds on the Fourier spectrum of \(\mathsf{AC}^0\)
- Unconditional pseudorandom generators for low degree polynomials
- What circuit classes can be learned with non-trivial savings?
- \(\Sigma_ 1^ 1\)-formulae on finite structures
Cited in
(7)- Paradigms for Unconditional Pseudorandom Generators
- Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates
- scientific article; zbMATH DE number 7528580 (Why is no real title available?)
- Quantified Derandomization: How to Find Water in the Ocean
- More on bounded independence plus noise: pseudorandom generators for read-once polynomials
- A polynomial-time construction of a hitting set for read-once branching programs of width 3
- A family of enhanced Lehmer random number generators, with hyperplane suppression, and direct support for certain physical applications
This page was built for publication: Improved pseudorandom generators from pseudorandom multi-switching lemmas
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5875501)
