A Polylogarithmic PRG for Degree $2$ Threshold Functions in the Gaussian Setting

Daniel M. Kane

We devise a new pseudorandom generator against degree 2 polynomial threshold functions in the Gaussian setting. We manage to achieve $\epsilon$ error with seed length polylogarithmic in $\epsilon$ and the dimension, and exponential improvement over previous constructions.

Knowledge Graph



Sign up or login to leave a comment