A Regularity Lemma, and Low-Weight Approximators, for Low-Degree Polynomial Threshold Functions
We give a "regularity lemma" for degree-d polynomial threshold functions (PTFs) over the Boolean cube {-1,1} <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> . Roughly speaking, this result shows that every degree-d PTF can be decomposed into a constant number of subfunctions such that almost all of the subfunctions are close to being regular PTFs. Here a "regular" PTF is a PTF sign(p(x)) where the influence of each variable on the polynomial p(x) is a small fraction of the total influence of p. As an application of this regularity lemma, we prove that for any constants d ≥ 1, ϵ > 0, every degree-d PTF over n variables can be approximated to accuracy eps by a constant degree PTF that has integer weights of total magnitude O(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">d</sup> ). This weight bound is shown to be optimal up to logarithmic factors.