scientific article; zbMATH DE number 7768373

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

Authors William M. Hoza

Publication date 20 November 2023

zbMATH Keywords

derandomizationspace complexityread-once branching programpseudorandom pseudodistributionweighted pseudorandom generator

Mathematics Subject Classification ID

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

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

(5)

• Paradigms for Unconditional Pseudorandom Generators
• Limitations of the Impagliazzo-Nisan-Wigderson pseudorandom generator against permutation branching programs
• Approximating iterated multiplication of stochastic matrices in small space
• Near-optimal derandomization of medium-width branching programs
• Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting)

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)