Random restrictions and PRGs for PTFs in Gaussian Space

Zander Kelley, Raghu Meka

A polynomial threshold function (PTF) $f:{\mathbb{R}}^n\to \mathbb{R}$ is a function of the form $f(x)=\mathsf{sign}(p(x))$ where $p$ is a polynomial of degree at most $d$…