A
Regularity Lemma, and Low-Weight Approximators, for
Low-Degree Polynomial Threshold Functions
Ilias Diakonikolas,
Rocco Servedio, Li-Yang Tan, Andrew Wan
25th Conference on Computational Complexity (CCC), 2010
Abstract:
We give a “regularity lemma” for degree-d polynomial threshold functions (PTFs) over the Boolean cube {-1,1}n. 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 ε by a constant-degree PTF that has integer weights of total magnitude O(nd). This weight bound is shown to be essentially optimal.
Preliminary version (updated March 15): [PDF]
Arxiv report: [arXiv]