STOC2020
Fooling Gaussian PTFs via local hyperconcentration
Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan
6 citations
Abstract
We give a pseudorandom generator that fools degree-d polynomial threshold functions over n-dimensional Gaussian space with seed length d O(logd) · logn. All previous generators had a seed length with at least a 2 d dependence on d.