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

Abstract

The Friedgut--Kalai--Naor theorem states that if a Boolean function $f:\{0,1{\}}^n\to \{0,1\}$ is close (in $L^2$-distance) to an affine function $\ell (x_1,...,x_n)=c_0+{\sum }_i{c}_i{x}_i$, 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 $\left(\genfrac{}{}{0ex}{}{[n]}{k}\right)=\{(x_1,...,x_n)\in \{0,1{\}}^n:{\sum }_i{x}_i=k\}$.

15 pages

References in corpus (1)

• Boolean functions whose Fourier transform is concentrated on pairwise disjoint subsets of the input

Cited by in corpus (3)

• Weightwise perfectly balanced functions with high weightwise nonlinearity profile
• Equivalent definitions for (degree one) Cameron-Liebler classes of generators in finite classical polar spaces
• Maximum Consensus by Weighted Influences of Monotone Boolean Functions