Noise stable halfspaces are close to very small juntas.
I. Diakonikolas and
R. Jaiswal and
R. Servedio and
L.-Y. Tan and
A. Wan.
Chicago Journal of Theoretical Computer Science, Volume 2015,
Article 4, 2015, pp. 1 -- 13.
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.
Link to open-access journal version.
Back to
main papers page