#

### 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.

- 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.