Constant-Error Pseudorandomness Proofs from Hardness Require Majority

DOI10.1145/3322815zbMath1495.68153WikidataQ114614013 ScholiaQ114614013MaRDI QIDQ5205815

Emanuele Viola

Publication date: 16 December 2019

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

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

zbMATH Keywords

lower bound; pseudorandom generator; majority; black box

Mathematics Subject Classification ID

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

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