A polynomial restriction lemma with applications

A polynomial threshold function (PTF) of degree <i>d</i> is a boolean function of the form <i>f</i>=<i>sgn</i>(<i>p</i>), where <i>p</i> is a degree-<i>d</i> polynomial, and <i>sgn</i> 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 <i>g</i> is called Î´-close to constant if, for some <i>v</i>â{1,â1}, we have <i>g</i>(<i>x</i>)=<i>v</i> for all but at most Î´ fraction of inputs. We show for every PTF <i>f</i> of degree <i>d</i>â¥ 1, and parameters 0<Î´, <i>r</i>â¤ 1/16, that 
<table class="display dcenter"><tr style="vertical-align:middle"><td class="dcell"><i>Pr</i><sub>Ïâ¼Â <i>R</i><sub><i>r</i></sub></sub>Â [<i>f</i><sub>Ï</sub>Â is not Â Î´Â -close to constant]Â â¤Â </td><td class="dcell">â</td><td class="dcell"><table style="border:0;border-spacing:1;border-collapse:separate;" class="cellpadding0"><tr><td class="hbar"></td></tr><tr><td style="text-align:center;white-space:nowrap" ><i>r</i></td></tr></table></td><td class="dcell">Â·Â (log<i>r</i><sup>â1</sup>Â Â·Â logÎ´<sup>â1</sup>)<sup><i>O</i>(<i>d</i><sup>2</sup>)</sup>,Â Â </td></tr></table> where Ïâ¼ <i>R</i><sub><i>r</i></sub> is a random restriction leaving each variable, independently, free with probability <i>r</i>, and otherwise assigning it 1 or â1 uniformly at random. In fact, we show a more general result for random <em>block</em> restrictions: given an arbitrary partitioning of input variables into <i>m</i> blocks, a random block restriction picks a uniformly random block ââ [<i>m</i>] and assigns 1 or â1, uniformly at random, to all variable outside the chosen block â. We prove the Block Restriction Lemma saying that a PTF <i>f</i> of degree <i>d</i> becomes Î´-close to constant when hit with a random block restriction, except with probability at most <i>m</i><sup>â1/2</sup> Â· (log<i>m</i>Â· logÎ´<sup>â1</sup>)<sup><i>O</i>(<i>d</i><sup>2</sup>)</sup>. As an application of our Restriction Lemma, we prove lower bounds against constant-depth circuits with PTF gates of any degree 1â¤ <i>d</i>âª âlog<i>n</i>/loglog<i>n</i>, generalizing the recent bounds against constant-depth circuits with linear threshold gates (LTF gates) proved by Kane and Williams (<em>STOC</em>, 2016) and Chen, Santhanam, and Srinivasan (<em>CCC</em>, 2016). In particular, we show that there is an <i>n</i>-variate boolean function <i>F</i><sub><i>n</i></sub> â <i>P</i> such that every depth-2 circuit with PTF gates of degree <i>d</i>â¥ 1 that computes <i>F</i><sub><i>n</i></sub> must have at least (<i>n</i><sup>3/2+1/<i>d</i></sup>)Â· (log<i>n</i>)<sup>â<i>O</i>(<i>d</i><sup>2</sup>)</sup> 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-<i>d</i> PTFs due to Kane (<em>Computational Complexity</em>, 2014), and the Littlewood-Offord type anticoncentration bound for degree-<i>d</i> multilinear polynomials due to Meka, Nguyen, and Vu (<em>Theory of Computing</em>, 2016). Finally, we give <em>derandomized</em> versions of our Block Restriction Lemma and Littlewood-Offord type anticoncentration bounds, using a pseudorandom generator for PTFs due to Meka and Zuckerman (<em>SICOMP</em>, 2013).