A Regularity Lemma, and low-weight approximators, for low-degree Polynomial Threshold Functions
I. Diakonikolas and R. Servedio and L.-Y. Tan and A. Wan.
In 25th Conference on Computational Complexity (CCC), 2010, pp. 211-222.


We give a ``regularity lemma'' for degree-$d$ polynomial threshold functions (PTFs) over the Boolean cube $\{-1,1\}^n$. 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 \geq 1, \eps > 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^d).$ This weight bound is shown to be nearly optimal.

pdf of conference version

pdf of full version

Back to main papers page