Pseudodistributions that beat all pseudorandom generators (extended abstract)

DOI10.4230/LIPICS.CCC.2021.33MaRDI QIDQ6115396zbMATH OpenOpenAlexFDO

Authors Edward Pyne, Salil Vadhan

Publication date 12 July 2023

Full work available at URL https://doi.org/10.4230/lipics.ccc.2021.33

zbMATH Keywords

pseudorandomnessspace-bounded computationspectral graph theory

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cited in

(10)

• Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting)
• Almost Optimal Pseudorandom Generators for Spherical Caps
• Paradigms for Unconditional Pseudorandom Generators
• Near-optimal derandomization of medium-width branching programs
• Approximating iterated multiplication of stochastic matrices in small space
• \(\mathrm{BPL}\subseteq\mathrm{L}\text{-}\mathrm{AC}^1\)
• Recursive error reduction for regular branching programs
• Pseudodistributions that beat all pseudorandom generators
• Implications of better PRGs for permutation branching programs
• On sums of INW pseudorandom generators

This page was built for publication: Pseudodistributions that beat all pseudorandom generators (extended abstract)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6115396)