FKN Theorem on the biased cube

Piotr Nayar. "FKN Theorem on the biased cube." Colloquium Mathematicae 137.2 (2014): 253-261. <http://eudml.org/doc/284353>.

@article{PiotrNayar2014,
abstract = {We consider Boolean functions defined on the discrete cube $\{-γ, γ^\{-1\}\}ⁿ$ equipped with a product probability measure $μ^\{⊗ n\}$, where $μ = βδ_\{-γ\} + αδ_\{γ^\{-1\}\}$ and γ = √(α/β). This normalization ensures that the coordinate functions $(x_i)_\{i=1,...,n\}$ are orthonormal in $L₂(\{-γ,γ^\{-1\}\}ⁿ,μ^\{⊗ n\})$. We prove that if the spectrum of a Boolean function is concentrated on the first two Fourier levels, then the function is close to a certain function of one variable. Our theorem strengthens the non-symmetric FKN Theorem due to Jendrej, Oleszkiewicz and Wojtaszczyk. Moreover, in the symmetric case α = β = 1/2 we prove that if a [-1,1]-valued function defined on the discrete cube is close to a certain affine function, then it is also close to a [-1,1]-valued affine function.},
author = {Piotr Nayar},
journal = {Colloquium Mathematicae},
keywords = {Boolean functions; Walsh-Fourier expansion; FKN theorem},
language = {eng},
number = {2},
pages = {253-261},
title = {FKN Theorem on the biased cube},
url = {http://eudml.org/doc/284353},
volume = {137},
year = {2014},
}

TY - JOUR
AU - Piotr Nayar
TI - FKN Theorem on the biased cube
JO - Colloquium Mathematicae
PY - 2014
VL - 137
IS - 2
SP - 253
EP - 261
AB - We consider Boolean functions defined on the discrete cube ${-γ, γ^{-1}}ⁿ$ equipped with a product probability measure $μ^{⊗ n}$, where $μ = βδ_{-γ} + αδ_{γ^{-1}}$ and γ = √(α/β). This normalization ensures that the coordinate functions $(x_i)_{i=1,...,n}$ are orthonormal in $L₂({-γ,γ^{-1}}ⁿ,μ^{⊗ n})$. We prove that if the spectrum of a Boolean function is concentrated on the first two Fourier levels, then the function is close to a certain function of one variable. Our theorem strengthens the non-symmetric FKN Theorem due to Jendrej, Oleszkiewicz and Wojtaszczyk. Moreover, in the symmetric case α = β = 1/2 we prove that if a [-1,1]-valued function defined on the discrete cube is close to a certain affine function, then it is also close to a [-1,1]-valued affine function.
LA - eng
KW - Boolean functions; Walsh-Fourier expansion; FKN theorem
UR - http://eudml.org/doc/284353
ER -