A regularity lemma, and low-weight approximators, for low-degree polynomial threshold functions

Details A regularity lemma, and low-weight approximators, for low-degree polynomial threshold functions A regularity lemma, and low-weight approximators, for low-degree polynomial threshold functions

2009-09-25

arxiv.org/abs/0909.4727v2

Computer Science

Computational Complexity

23 pages, 0 figures

Scientific paper

We give a "regularity lemma" for degree-d polynomial threshold functions (PTFs) over the Boolean cube {-1,1}^n. 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 \geq 0, every degree-d PTF over n variables has 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 constant factors.

Affiliated with

Also associated with

No associations

Rating

A regularity lemma, and low-weight approximators, for low-degree polynomial threshold functions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A regularity lemma, and low-weight approximators, for low-degree polynomial threshold functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A regularity lemma, and low-weight approximators, for low-degree polynomial threshold functions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-326281