On the Distribution of the Fourier Spectrum of Halfspaces

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

Research output: Contribution to journalArticlepeer-review

Abstract

Bourgain showed that any noise stable Boolean function ƒ 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 ƒ is a halfspace.
Original languageEnglish
JournalComputing Research Repository (CoRR)
Volumeabs/1202.6680
Publication statusPublished - 2012

Fingerprint

Dive into the research topics of 'On the Distribution of the Fourier Spectrum of Halfspaces'. Together they form a unique fingerprint.

Cite this