Bounding the Sensitivity of Polynomial Threshold Functions

Computer Science – Computational Complexity

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Fixed an important flaw. Some proofs are simplified from last version

Scientific paper

We give the first non-trivial upper bounds on the average sensitivity and noise sensitivity of polynomial threshold functions. More specifically, for a Boolean function f on n variables equal to the sign of a real, multivariate polynomial of total degree d we prove 1) The average sensitivity of f is at most O(n^{1-1/(4d+6)}) (we also give a combinatorial proof of the bound O(n^{1-1/2^d}). 2) The noise sensitivity of f with noise rate \delta is at most O(\delta^{1/(4d+6)}). Previously, only bounds for the linear case were known. Along the way we show new structural theorems about random restrictions of polynomial threshold functions obtained via hypercontractivity. These structural results may be of independent interest as they provide a generic template for transforming problems related to polynomial threshold functions defined on the Boolean hypercube to polynomial threshold functions defined in Gaussian space.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Bounding the Sensitivity of 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 Bounding the Sensitivity of Polynomial Threshold Functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bounding the Sensitivity of Polynomial Threshold Functions will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-235848

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.