Friedgut--Kalai--Naor theorem for slices of the Boolean cube

Original · EN

The Friedgut--Kalai--Naor theorem states that if a Boolean function f {0,1}ⁿ → {0,1} is close (in L²-distance) to an affine function ℓ(x₁,...,xₙ) = c₀ + ∑ᵢ cᵢ xᵢ, 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 [n]k = {(x₁,...,xₙ) ∈ {0,1}ⁿ: ∑ᵢ xᵢ = k }.