On the Distribution of the Fourier Spectrum of Halfspaces

Andrew Wan; Ilias Diakonikolas; Li-Yang Tan; Ragesh Jaiswal; Rocco A. Servedio

arxiv: 1202.6680 · v1 · pith:YZL6NBCXnew · submitted 2012-02-29 · 💻 cs.CC · cs.DM· math.PR

On the Distribution of the Fourier Spectrum of Halfspaces

Ilias Diakonikolas , Ragesh Jaiswal , Rocco A. Servedio , Li-Yang Tan , Andrew Wan This is my paper

classification 💻 cs.CC cs.DMmath.PR

keywords bourgainadditionalassumptionbooleandistributionexponentialfourierfunction

0 comments

read the original abstract

Bourgain showed that any noise stable Boolean function $f$ can be well-approximated by a junta. In this note we give an exponential sharpening of the parameters of Bourgain's result under the additional assumption that $f$ is a halfspace.

This paper has not been read by Pith yet.

On the Distribution of the Fourier Spectrum of Halfspaces

discussion (0)