Randomness-efficient sampling within NC\(^{1}\)

DOI10.1007/S00037-007-0238-5zbMath1149.68027OpenAlexW3022367360MaRDI QIDQ937194

Alexander D. Healy

Publication date: 20 August 2008

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-007-0238-5

zbMATH Keywords

derandomizationpseudorandomnessconstant-depth circuitsrandom walks on expander graphs

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (6)

A Hoeffding inequality for Markov chains ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A PCP Characterization of AM ⋮ Random walks on rotating expanders ⋮ Superfast coloring in CONGEST via efficient color sampling

This page was built for publication: Randomness-efficient sampling within NC\(^{1}\)