pith. sign in

arxiv: 1410.7834 · v3 · pith:WLNC5NHYnew · submitted 2014-10-28 · 🧮 math.CO

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

classification 🧮 math.CO
keywords booleanfunctiontheoremaffineclosefriedgut--kalai--naorbinomcolon
0
0 comments X
read the original abstract

The Friedgut--Kalai--Naor theorem states that if a Boolean function $f\colon \{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 $\binom{[n]}{k} = \{(x_1,...,x_n) \in \{0,1\}^n : \sum_i x_i = k \}$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.