Fooling Gaussian PTFs via Local Hyperconcentration.
R. O'Donnell and R. Servedio and L.-Y. Tan.
In 52nd Annual Symposium on Theory of Computing (STOC), 2020, to appear.


Abstract:

We give a pseudorandom generator that fools degree-d polynomial threshold functions over n-dimensional Gaussian space with seed length dO(log d) log n. All previous generators had a seed length with at least a 2d dependence on d.

The key new ingredient is our Local Hyperconcentration Theorem, which shows that every degree-d Gaussian polynomial is hyperconcentrated almost everywhere at scale d-O(log d).


Back to main papers page