A Small PRG for Polynomial Threshold Functions of Gaussians

Abstract

We develop a pseudo-random generator to fool degree-$d$ polynomial threshold functions with respect to the Gaussian distribution. For $c>0$ any constant, we construct a pseudo-random generator that fools such functions to within $\epsilon$ and has seed length $\log (n)2^{O(d)}{\epsilon }^{-4-c}$.

Cited by in corpus (2)

• Open Problems in Analysis of Boolean Functions
• Pseudorandomness for concentration bounds and signed majorities