scientific article; zbMATH DE number 7768373

DOI10.4230/LIPICS.APPROX/RANDOM.2021.28MaRDI QIDQ6090903zbMATH OpenFDO

Authors William M. Hoza

Publication date 20 November 2023

Full work available at URL https://doi.org/10.4230/LIPICS.APPROX/RANDOM.2021.28

zbMATH Keywords

derandomizationpseudorandom pseudodistributionread-once branching programspace complexityweighted pseudorandom generator

Mathematics Subject Classification ID

Randomized algorithms (68W20) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Recommendations

• scientific article; zbMATH DE number 1301964
• scientific article; zbMATH DE number 7701432
• Pseudorandom generators for space-bounded computation
• Lower space bounds for randomized computation
• Typically-correct derandomization for small time and space
• Space-bounded hierarchies and probabilistic computations

Cited in

(9)

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

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