Volume 10 (2014) Article 2 pp. 27-53

A Regularity Lemma and Low-Weight Approximators for Low-Degree Polynomial Threshold Functions

by Ilias Diakonikolas, Rocco A. Servedio, Li-Yang Tan, and Andrew Wan

Received: September 8, 2012
Revised: September 27, 2013
Published: March 25, 2014

$ \newcommand{\sign}{{\mathrm{sign}}} $

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.

DOI: 10.4086/toc.2014.v010a002

© 2014 Ilias Diakonikolas, Rocco A. Servedio, Li-Yang Tan, and Andrew Wan
Licensed under a Creative Commons Attribution License (CC-BY)