Randomness-Efficient Sampling Within NC 1

DOI10.1007/11830924_37MaRDI QIDQ3595383zbMATH OpenOpenAlexFDO

Authors Alexander D. Healy

Publication date 28 August 2007

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11830924_37

Mathematics Subject Classification ID

Randomized algorithms (68W20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Randomness-efficient sampling within NC\(^{1}\)
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Randomness extraction in \(\mathsf{AC}^0\) and with small locality
• On ε‐biased generators in NC⁰
• scientific article; zbMATH DE number 1559537

Cited in

(6)

• Basic Facts about Expander Graphs
• Simulating (log ^c n )-wise independence in NC
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error
• Randomness-efficient sampling within NC\(^{1}\)
• On the randomness complexity of efficient sampling

This page was built for publication: Randomness-Efficient Sampling Within NC 1

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