Published by the Department of Computer Science, The University of Chicago.
Noise Stable Halfspaces are Close to Very Small Juntas
University of Edinburgh
ilias.d AT ed DOT ac DOT uk
New Delhi, India
rjaiswal AT cse DOT iit DOT ac DOT in
Rocco A. Servedio
New York, NY, USA
rocco AT cs DOT columbia DOTedu
Chicago, Illinois, USA
liyang AT ttic DOT edu
October 19, 2015
Institute for Defense Analyses
Alexandria, VA, USA
atw AT columbia DOT edu
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.
- The article: PDF (281 KB)
- Source material: ZIP (234 KB)
- BibTeX entry for this
article (339 bytes)
Submitted March 5, 2013, revised November 11, 2014, and in final form
October 6, 2015, published October 19, 2015.
Volume 2016 Article 1