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.


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