Noise Stable Halfspaces are Close to Very Small Juntas

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

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

Bourgain showed that any noise stable Boolean function ff 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 ff is a halfspace.
Original languageEnglish
Article number4
Pages (from-to)1-13
Number of pages13
JournalChicago Journal of Theoretical Computer Science
Volume2015
DOIs
Publication statusPublished - 19 Oct 2015

Fingerprint

Dive into the research topics of 'Noise Stable Halfspaces are Close to Very Small Juntas'. Together they form a unique fingerprint.

Cite this