A polynomial restriction lemma with applications

A polynomial threshold function (PTF) of degree d is a boolean function of the form f = sgn ( p ), where p is a degree- d polynomial, and 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 δ-close to constant if, for some v ε{1,-1}, we have g ( x )= v for all but at most δ fraction of inputs. We show for every PTF f of degree d ≥ 1, and parameters 0<δ, r ≤ 1/16, that Pr ∾ R r [ f ρ is not δ-close to constant] ≤ √ #183;(log r -1 · log δ-1 ) O ( d 2 ) , where ρ ∾ 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 ℓΕ [ m ] 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 f of degree d becomes δ-close to constant when hit with a random block restriction, except with probability at most m -1/2 #183; (log m #183; logδ -1 ) 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≤ d ≪ √log n /loglog 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 Ε P such that every depth-2 circuit with PTF gates of degree d ≥ 1 that computes F n must have at least ( n 3/2+1/ d )#183; (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).

Authors

• Valentine Kabanets
• Daniel M. Kane
• Zhenjian Lu

Keywords

• Littlewood-Offord
• PTF circuits
• circuit lower bounds
• polynomial threshold functions
• random restrictions