The Gaussian Surface Area and Noise Sensitivity of Degree-$d$ Polynomials

Details The Gaussian Surface Area and Noise Sensitivity of Degree-$d$ Polynomials The Gaussian Surface Area and Noise Sensitivity of Degree-$d$ Polynomials

2009-12-14

arxiv.org/abs/0912.2709v1

Computer Science

Computational Complexity

Scientific paper

We provide asymptotically sharp bounds for the Gaussian surface area and the Gaussian noise sensitivity of polynomial threshold functions. In particular we show that if $f$ is a degree-$d$ polynomial threshold function, then its Gaussian sensitivity at noise rate $\epsilon$ is less than some quantity asymptotic to $\frac{d\sqrt{2\epsilon}}{\pi}$ and the Gaussian surface area is at most $\frac{d}{\sqrt{2\pi}}$. Furthermore these bounds are asymptotically tight as $\epsilon\to 0$ and $f$ the threshold function of a product of $d$ distinct homogeneous linear functions.

Affiliated with

Also associated with

No associations

Rating

The Gaussian Surface Area and Noise Sensitivity of Degree-$d$ Polynomials 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 The Gaussian Surface Area and Noise Sensitivity of Degree-$d$ Polynomials, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Gaussian Surface Area and Noise Sensitivity of Degree-$d$ Polynomials will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-624977