scientific article; zbMATH DE number 7561734

DOI10.4230/LIPICS.CCC.2020.6MaRDI QIDQ5092453zbMATH OpenFDO

Authors Dean Doron, Pooya Hatami, William M. Hoza

Publication date 21 July 2022

Full work available at URL https://doi.org/10.4230/LIPICS.CCC.2020.6

zbMATH Keywords

parity gatespseudorandom generatorspseudorandom restrictionsread-once depth-2 formulas

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites work

• \(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\)
• \(\text{RL}\subseteq \text{SC}\)
• Bounded independence plus noise fools products
• Concentration for limited independence via inequalities for the elementary symmetric polynomials
• Fourier bounds and pseudorandom generators for product tests
• Improved algorithms via approximations of probability distributions
• Improved pseudorandom generators for depth 2 circuits
• Improved pseudorandomness for unordered branching programs through local monotonicity
• Near-optimal pseudorandom generators for constant-depth read-once formulas
• Pseudorandom generators for group products, extended abstract
• Pseudorandom generators for regular branching programs
• Pseudorandom generators for space-bounded computation
• Pseudorandom generators for width-3 branching programs
• Pseudorandom pseudo-distributions with near-optimal error for read-once branching programs
• Pseudorandomness and Fourier-growth bounds for width-3 branching programs
• Pseudorandomness for network algorithms
• Pseudorandomness for regular branching programs via Fourier analysis
• Randomness is linear in space
• Simple Constructions of Almost k-wise Independent Random Variables
• Simple optimal hitting sets for small-success RL
• Small-bias is not enough to hit read-once CNF
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Space pseudorandom generators by communication complexity lower bounds
• Undirected connectivity in log-space

Cited in

(6)

• scientific article; zbMATH DE number 1759796 (Why is no real title available?)
• Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace
• Paradigms for Unconditional Pseudorandom Generators
• Pseudorandomness, symmetry, smoothing: I
• A variant of Maclaurin's inequality
• Approximate independence of permutation mixtures

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 Q5092453)