Pseudorandom generators for polynomial threshold functions

DOI10.1137/100811623MaRDI QIDQ6828890zbMATH OpenFDO

Authors Raghu Meka, David Zuckerman

Publication date 25 September 2013

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/100811623

zbMATH Keywords

branching programshalfspacesinvariance principlespolynomialspseudorandom generatorsthreshold functions

Mathematics Subject Classification ID

Functional limit theorems; invariance principles (60F17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Cited in

(2)

• Pseudorandom generators for unbounded-width permutation branching programs
• Fooling near-maximal decision trees

This page was built for publication: Pseudorandom generators for polynomial threshold functions

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