We give a pseudorandom generator that fools degree-d polynomial threshold functions over n-dimensional Gaussian space with seed length d^{O(log d)} log n. All previous generators had a seed length with at least a 2^d 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