Chicago Journal of Theoretical Computer Science

Volume 2016

Article 14

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


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

Yuval Filmus
Computer Science Department
Technion, Israel Institute of Technology
Haifa, Israel
yuvalfi AT cs DOT technion DOT ac DOT il

October 22, 2016

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.

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