Published by the Department of Computer Science, The University of Chicago.

Abstract

The Friedgut--Kalai--Naor theorem, a basic result in the field of analysis of Boolean functions, states that if a Boolean function on the Boolean cube $\{0,1\}^n$ is close to a function of the form $c_0 + \sum_i c_i x_i$, then it is close to a dictatorship (a function depending on a single coordinate). We prove an analogous theorem for functions defined on the slice $\binom{[n]}{k} = \{ (x_1,\ldots,x_n) \in \{0,1\}^n : \sum_i x_i = k \}$.

When $k/n$ is bounded away from $0$ and $1$, our theorem states that if a function on the slice is close to a function of the form $\sum_i c_i x_i$ then it is close to a dictatorship. When $k/n$ is close to $0$ or to $1$, we can only guarantee being close to a junta (a function depending on a small number of coordinates); this deterioration in the guarantee is unavoidable, since for small $p$ a maximum of a small number of variables is close to their sum.

Kindler and Safra proved an FKN theorem for the biased Boolean cube, in which the underlying measure is the product measure $\mu_p(x) = p^{\sum_i x_i} (1-p)^{\sum_i (1-x_i)}$. As a corollary of our FKN theorem for the slice, we deduce a uniform version of the FKN theorem for the biased Boolean cube, in which the error bounds depend uniformly on $p$. Mirroring the situation on the slice, when $p$ is very close to $0$ or to $1$, we can only guarantee closeness to a junta.

• The article: PDF (271 KB)
• Source material: ZIP (85 KB)
• BibTeX entry for this article (310 bytes)

Submitted October 7, 2014, revised May 1st, 2016, published October 22, 2016.

DOI: 10.4086/cjtcs.2016.014
© Yuval Filmus
Licensed under a Creative Commons Attribution License




---

Volume 2016, Article 13 Volume 2017, Article 1
Volume 2016 Published articles