Chicago Journal of Theoretical Computer Science

Volume 2015

Article 4

Published by the Department of Computer Science, The University of Chicago.

Noise Stable Halfspaces are Close to Very Small Juntas

Ilias Diakonikolas
University of Edinburgh
Edinburgh, UK
ilias.d AT ed DOT ac DOT uk

Ragesh Jaiswal
IIT Delhi
New Delhi, India
rjaiswal AT cse DOT iit DOT ac DOT in

Rocco A. Servedio
Columbia University
New York, NY, USA
rocco AT cs DOT columbia DOTedu

Li-Yang Tan
Chicago, Illinois, USA
liyang AT ttic DOT edu

Andrew Wan
Institute for Defense Analyses
Alexandria, VA, USA
atw AT columbia DOT edu

October 19, 2015


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.

Submitted March 5, 2013, revised November 11, 2014, and in final form October 6, 2015, published October 19, 2015.

doi: 10.4086/cjtcs.2015.004

[] Article 3 [] Volume 2016 Article 1
[back] Volume 2015 [back] Published articles
[CJCTS home]