scientific article; zbMATH DE number 7528580
From MaRDI portal
Publication:5077146
Recommendations
- Improved pseudorandom generators from pseudorandom multi-switching lemmas
- An improved derandomization of the switching lemma
- Improved pseudorandom generators for depth 2 circuits
- scientific article; zbMATH DE number 1952891
- Improved pseudorandom generators for combinatorial rectangles
- Pseudorandom generators without the XOR lemma (extended abstract)
- Pseudorandom Generators and Typically-Correct Derandomization
- An improved pseudo-random generator based on the discrete logarithm problem
- Improved bounds in the multiple-recursive matrix method for pseudorandom number and vector generation
- On a multiplicative generator of pseudorandom numbers
Cites work
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- A simple proof of Bazzi's theorem
- An average-case depth hierarchy theorem for Boolean circuits
- 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
- Computational Complexity
- 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
- scientific article; zbMATH DE number 6351503 (Why is no real title available?)
- 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 1833418 (Why is no real title available?)
- scientific article; zbMATH DE number 5485586 (Why is no real title available?)
- Improved pseudorandom generators for depth 2 circuits
- Improved pseudorandom generators from pseudorandom multi-switching lemmas
- 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 derandomizing algorithms that err extremely rarely
- On deterministic approximation of DNF
- On polynomial approximations to \(\mathrm{AC}^0\)
- On Small-depth Frege Proofs for Tseitin for Grids
- 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
- Pseudorandom Bits for Constant‐Depth Circuits with Few Arbitrary Symmetric Gates
- Pseudorandom bits for polynomials
- Pseudorandom generators for low degree polynomials
- Pseudorandom generators for width-3 branching programs
- Pseudorandom generators from polarizing random walks
- Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates
- Pseudorandomness for regular branching programs via Fourier analysis
- 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 average sensitivity of bounded-depth formulas
- 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?
- With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
Cited in
(3)
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5077146)
