Pseudorandom Generators with Optimal Seed Length for Non-Boolean Poly-Size Circuits

DOI10.1145/3018057zbMath1427.68111MaRDI QIDQ4973883

Sergei Artemenko, Ronen Shaltiel

Publication date: 6 December 2019

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3018057

zbMATH Keywords

pseudorandom generators; pseudorandomness; hardness versus randomness; randomness complexity of sampling

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

65C10: Random number generation in numerical analysis

94A17: Measures of information, entropy

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W20: Randomized algorithms

94C11: Switching theory, applications of Boolean algebras to circuits and networks

68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)