期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2017
卷号：2017
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 ] ( r + ) ( log (1 r ) 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 + ) ( log m 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 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 P such that every depth-2 circuit with PTF gates of degree d 1 that computes F n must have at least n 2 3 + 1 d ( 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).
