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.