Friedgut-Kalai-Naor Theorem for Slices of the Boolean Cube.

Abstract

The Friedgut–Kalai–Naor theorem states that if a Boolean function f: {±1}n → {±1} is close (in L2-distance) to an affine function `(x1,..., xn) = c0+ i cixi, then f is close to a Boolean affine function (which necessarily depends on at most one coordinate). We prove a similar theorem for functions defined over