A polynomial threshold function (PTF) of degree $d$ is a boolean function of the form $f=\mathrm{sgn}(p)$, where $p$ is a degree-$d$ polynomial, and $\mathrm{sgn}$ is the sign function. The main result of the paper is an almost optimal bound on the probability that a random restriction of a PTF is not close to a constant function, where a boolean function $g$ is called $\delta$-close to constant if, for some $v\in\{1,-1\}$, we have $g(x)=v$ for all but at most $\delta$ fraction of inputs. We show for every PTF $f$ of degree $d\geq 1$, and parameters $0<\delta, r\leq 1/16$, that \[\mathbf{Pr}_{\rho\sim R_r} [f_{\rho} \text{ is not } \delta \text{-close to constant}] \leq (\sqrt{r} + \delta)\cdot (\log (1/r) \cdot \log (1/\delta))^{O(d^2)},\] where $\rho\sim R_r$ is a random restriction leaving each variable, independently, free with probability $r$, and otherwise assigning it $1$ or $-1$ uniformly at random. In fact, we show a more general result for random block restrictions: given an arbitrary partitioning of input variables into $m$ blocks, a random block restriction picks a uniformly random block $\ell\in [m]$ and assigns $1$ or $-1$, uniformly at random, to all variable outside the chosen block $\ell$. We prove the Block Restriction Lemma saying that a PTF $f$ of degree $d$ becomes $\delta$-close to constant when hit with a random block restriction, except with probability at most $(m^{-1/2}+\delta)\cdot (\log m\cdot \log (1/\delta))^{O(d^2)}$.

As an application of our Restriction Lemma, we prove lower bounds against constant-depth circuits with PTF gates of any degree $1\leq d\ll \sqrt{\log n/\log\log n}$, generalizing the recent bounds against constant-depth circuits with linear threshold gates (LTF gates) proved by Kane and Williams (STOC, 2016) and Chen, Santhanam, and Srinivasan (CCC, 2016). In particular, we show that there is an $n$-variate boolean function $F_n \in \mathrm{P}$ such that every depth-2 circuit with PTF gates of degree $d\geq 1$ that computes $F_n$ must have at least $\left(n^{\frac{3}{2}+\frac{1}{d}}\right)\cdot (\log n)^{-O(d^2)}$ wires. For constant depths greater than $2$, we also show average-case lower bounds for such circuits with super-linear number of wires. These are the first super-linear bounds on the number of wires for circuits with PTF gates. We also give short proofs of the optimal-exponent average sensitivity bound for degree-$d$ PTFs due to Kane (Computational Complexity, 2014), and the Littlewood-Offord type anticoncentration bound for degree-$d$ multilinear polynomials due to Meka, Nguyen, and Vu (Theory of Computing, 2016).

Finally, we give derandomized versions of our Block Restriction Lemma and Littlewood-Offord type anticoncentration bounds, using a pseudorandom generator for PTFs due to Meka and Zuckerman (SICOMP, 2013).