Abstract:

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

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).