Theory of Computing
-------------------
Title     : A Regularity Lemma and Low-Weight Approximators for Low-Degree Polynomial Threshold Functions
Authors   : Ilias Diakonikolas, Rocco A. Servedio, Li-Yang Tan, and Andrew Wan
Volume    : 10
Number    : 2
Pages     : 27-53
URL       : https://theoryofcomputing.org/articles/v010a002

Abstract
--------

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, \epsilon > 0$, every degree-$d$ PTF over $n$
variables can be approximated to accuracy $\epsilon$ by a constant-degree
PTF that has integer weights of total magnitude $O_{\epsilon,d}(n^d)$.
This weight bound is shown to be optimal up to logarithmic factors.

A conference version of this paper appeared in the Proc.
25th Ann. IEEE Conf. on Computational Complexity, CCC 2010
(http://dx.doi.org/10.1109/CCC.2010.28).