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

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 >= 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 optimal up to logarithmic factors.
Original languageEnglish
Title of host publication2010 IEEE 25th Annual Conference on Computational Complexity (CCC)
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages211-222
Number of pages12
ISBN (Electronic)978-1-4244-7215-4
ISBN (Print)978-1-4244-7214-7
DOIs
Publication statusPublished - Jun 2010

Fingerprint

Dive into the research topics of 'A Regularity Lemma, and Low-Weight Approximators, for Low-Degree Polynomial Threshold Functions'. Together they form a unique fingerprint.

Cite this