CJTCS Volume 2015 Article 4

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
TTI-Chicago
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

Abstract

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.

doi: 10.4086/cjtcs.2015.004

Licensed under a Creative Commons Attribution License

Article 3

Volume 2016 Article 1
[back]

Volume 2015 [back]

Published articles