Geodesic
Boolean functions on $S_n$ which are nearly linear
Discrete analysis (2021)
Cet article a éte moissonné depuis la source Scholastica

Voir la notice de l'article

We show that if $f\colon S_n \to \{0,1\}$ is $ε$-close to linear in $L_2$ and $\mathbb{E}[f] \leq 1/2$ then $f$ is $O(ε)$-close to a union of "mostly disjoint" cosets, and moreover this is sharp: any such union is close to linear. This constitutes a sharp Friedgut-Kalai-Naor theorem for the symmetric group. Using similar techniques, we show that if $f\colon S_n \to \mathbb{R}$ is linear, $\Pr[f \notin \{0,1\}] \leq ε$, and $\Pr[f = 1] \leq 1/2$, then $f$ is $O(ε)$-close to a union of mostly disjoint cosets, and this is also sharp; and that if $f\colon S_n \to \mathbb{R}$ is linear and $ε$-close to $\{0,1\}$ in $L_\infty$ then $f$ is $O(ε)$-close in $L_\infty$ to a union of disjoint cosets.
Publié le : 
@article{DAS_2021_a1,
     author = {Yuval Filmus},
     title = {Boolean functions on $S_n$ which are nearly linear},
     journal = {Discrete analysis},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DAS_2021_a1/}
}
TY  - JOUR
AU  - Yuval Filmus
TI  - Boolean functions on $S_n$ which are nearly linear
JO  - Discrete analysis
PY  - 2021
UR  - http://geodesic.mathdoc.fr/item/DAS_2021_a1/
LA  - en
ID  - DAS_2021_a1
ER  - 
%0 Journal Article
%A Yuval Filmus
%T Boolean functions on $S_n$ which are nearly linear
%J Discrete analysis
%D 2021
%U http://geodesic.mathdoc.fr/item/DAS_2021_a1/
%G en
%F DAS_2021_a1
Yuval Filmus. Boolean functions on $S_n$ which are nearly linear. Discrete analysis (2021). http://geodesic.mathdoc.fr/item/DAS_2021_a1/