Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js
pdf icon
Volume 10 (2014) Article 2 pp. 27-53
A Regularity Lemma and Low-Weight Approximators for Low-Degree Polynomial Threshold Functions
Received: September 8, 2012
Revised: September 27, 2013
Published: March 25, 2014
Download article from ToC site:
[PDF (349K)] [PS (1442K)] [Source ZIP]
Keywords: complexity theory, Boolean functions, polynomials, threshold functions
ACM Classification: F.1.3, G.2.0
AMS Classification: 68Q15, 68R01

Abstract: [Plain Text Version]

\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.