Constant-Error Pseudorandomness Proofs from Hardness Require Majority

DOI10.1145/3322815zbMATH Open1495.68153OpenAlexW2952749817WikidataQ114614013 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 boundpseudorandom generatormajorityblack box

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (3)

Hardness Amplification Proofs Require Majority ⋮ Pseudorandom generators without the XOR lemma ⋮ Constant-space, constant-randomness verifiers with arbitrarily small error

This page was built for publication: Constant-Error Pseudorandomness Proofs from Hardness Require Majority

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