Noise Stable Halfspaces are Close to Very Small Juntas

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

doi:10.4086/cjtcs.2015.004

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 journal › Article › peer-review

Abstract

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 language	English
Article number	4
Pages (from-to)	1-13
Number of pages	13
Journal	Chicago Journal of Theoretical Computer Science
Volume	2015
DOIs	https://doi.org/10.4086/cjtcs.2015.004
Publication status	Published - 19 Oct 2015

Access to Document

10.4086/cjtcs.2015.004

cj15-04Final published version, 274 KBLicence: Creative Commons: Attribution (CC-BY)

http://cjtcs.cs.uchicago.edu/articles/2016/4/contents.htmlLicence: Creative Commons: Attribution (CC-BY)

Cite this

@article{33f46f6281b64de681f705ccfd8e8b5d,

title = "Noise Stable Halfspaces are Close to Very Small Juntas",

abstract = "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.",

author = "Ilias Diakonikolas and Ragesh Jaiswal and Servedio, {Rocco A.} and Li-Yang Tan and Andrew Wan",

year = "2015",

month = oct,

day = "19",

doi = "10.4086/cjtcs.2015.004",

language = "English",

volume = "2015",

pages = "1--13",

journal = "Chicago Journal of Theoretical Computer Science",

issn = "1073-0486",

publisher = "University of Chicago Press",

}

TY - JOUR

T1 - Noise Stable Halfspaces are Close to Very Small Juntas

AU - Diakonikolas, Ilias

AU - Jaiswal, Ragesh

AU - Servedio, Rocco A.

AU - Tan, Li-Yang

AU - Wan, Andrew

PY - 2015/10/19

Y1 - 2015/10/19

N2 - 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.

AB - 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.

U2 - 10.4086/cjtcs.2015.004

DO - 10.4086/cjtcs.2015.004

M3 - Article

SN - 1073-0486

VL - 2015

SP - 1

EP - 13

JO - Chicago Journal of Theoretical Computer Science

JF - Chicago Journal of Theoretical Computer Science

M1 - 4

ER -

Noise Stable Halfspaces are Close to Very Small Juntas

Abstract

Access to Document

Fingerprint

Cite this